## 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**

**Abstract:**

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(n*^{3}), 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(n*^{5}), 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**

**Abstract:**

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.