Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 '10 at 1:59
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
The implementation mentioned already is available at this site. It is a C++ library with a straight-forward interface. –  Xammy Jun 6 '12 at 7:14
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.