Welcome to MathOverflow

Question

11

1

One of the consequences of Seymour's characterization of regular matroids is the existence of a polynomial time recognition algorithm for totally unimodular matrices (i.e. matrices for which every square sub-determinant is in {0, 1, -1}).

But has anyone actually implemented it?

flag	asked Jun 7 2010 at 13:05 gordon-royle 2,677●9●20

I guess I'll take the silence as a probable "no"... It seems like something that I would like to have done, but don't actually want to do.. – gordon-royle Jun 8 2010 at 1:59

S. Sra · Accepted Answer · 2012-03-02 05:30:51Z UTC

EDIT. Walter and Trümper have announced on arXiv their implementation, with source code available, of two methods for testing total unimodularity. Their paper describes the technical details of the implementation / algorithm, and also provides several experimental results.

I found the following link for an implementation in R, where they claim to have a function for testing whether a matrix is totally unimodular. I have not checked which particular algorithm they use.

Link: R package

leonidas · Answer 2 · 2010-09-24 09:35:10Z UTC

5

To my knowledge no one has implemented the algorithm. A good reference though for someone thinking about it would be Truember's book "Matroid Decomposition" which contains a fairly simple description of the necessary steps.

answered Sep 24 2010 at 9:35

leonidas
51●1●1

Xammy · Answer 3 · 2012-06-06 07:14:25Z UTC

3

Since I cannot comment: The implementation mentioned already is available at this site. It is a C++ library with a straight-forward interface.

answered Jun 6 at 7:14

Xammy
31●1

Has anyone implemented a recognition algorithm for totally unimodular matrices?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.