16
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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.. $\endgroup$
    – Gordon Royle
    Jun 8, 2010 at 1:59

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ The implementation mentioned already is available at this site. It is a C++ library with a straight-forward interface. $\endgroup$
    – Xammy
    Jun 6, 2012 at 7:14
  • $\begingroup$ The link in @Xammy's comment is outdated. The C++ library can now be found here. $\endgroup$
    – Aaron Dall
    Jul 29, 2017 at 0:00
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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