Contributed Session Wed.1.H 3005

Wednesday, 10:30 - 12:00 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Algorithm for matrices and matroids


Chair: Klaus Truemper



Wednesday, 10:30 - 10:55 h, Room: H 3005, Talk 1

Matthias Walter
A simple algorithm for testing total unimodularity of matrices

Coauthor: Klaus Truemper


There is a significant practical need for an effective test of
total unimodularity of matrices. The currently fastest algorithm
for that task has complexity O(n3), where n is the longer
dimension of the given matrix. The algorithm would be
an excellent candidate for implementation, were it not for
numerous structurally complicated cases in several steps
that defy implementation with reasonable effort.
We have simplified the algorithm so that
all complicated cases are avoided while
key ideas are retained. The resulting, much simpler,
algorithm has complexity O(n5), which matches or is close
to that of other polynomial testing algorithms of total unimodularity.
The talk describes the simplified algorithm, compares it with
the original one, sketches an implementation, and summarizes
computational results for several classes of matrices.
The public-domain code is available from several websites.



Wednesday, 11:00 - 11:25 h, Room: H 3005, Talk 2

Leonidas E.L.K.E. A.P.TH Pitsoulis
Decomposition of binary signed-graphic matroids

Coauthor: Kostas Papalamprou


We employ Tutte's theory of bridges to derive a decomposition theorem for binary matroids arising from
signed graphs. The proposed decomposition differs from previous decomposition results on matroids that have
appeared in the literature in the sense that it is not based on k-sums, but rather on the operation of deletion of a cocircuit.
Specifically, it is shown that certain minors resulting from the deletion of a cocircuit of a binary matroid will be graphic matroids
apart from exactly one that will be signed-graphic, if and only if the matroid is signed-graphic.


  signature loans . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.