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.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.