A decomposition theory for matroids. V: Testing of matrix total unimodularity
type: Item
instance of: scholarly article
title: A decomposition theory for matroids. V: Testing of matrix total unimodularity
zbMATH Open document ID: 0646.05014
DOI: 10.1016/0095-8956(90)90030-4
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: We present an \(O((m+n)^ 3)\) algorithm for deciding total unimodularity of any real \(m\times n\) matrix, i.e., for deciding whether or not every square submatrix of the given matrix has determinant O or \(\pm 1\). The algorithm relies on the well-known reduction to the binary case, but from then on is quite different from any method we know of, in particular from the prior algorithm by W. H. Cunningham and J. Edmonds, and the recent algorithm by R. E. Bixby, W. H. Cunningham and A. Rajan, which are of order \(O((m+n)^ 5)\) and \(O((m+n)^{4.5}(\log (m+n))^{0.5})\), respectively. The most difficult part of the algorithm, where regularity of a 3- connected, binary, nongraphic and noncographic matroid must be decided, is handled by a search procedure that relies on the concept of induced decompositions of Parts III and IV. The efficacy of that search procedure crucially depends on asymmetries between certain circuit results and cocircuit results of graphs. In other settings these asymmetries can be quite annoying, but here they turn out to be most beneficial.
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 4053634
zbMATH Keywords: decomposition
zbMATH Keywords: matroid
author: Klaus Truemper
MaRDI profile type: Publication
full work available at URL: 0095-8956(90)90030-4
OpenAlex ID: W1992996900
cites work: Q5737094
cites work: A Combinatorial Decomposition Theory
cites work: Decomposition of regular matroids
cites work: On Whitney's 2‐isomorphism theorem for graphs
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids
cites work: On the efficiency of representability tests for matroids
cites work: Partial matroid representations
cites work: A decomposition theory for matroids. IV: Decomposition of graphs
cites work: On matroid separations of graphs
cites work: Connectivity in Matroids
Recommended article: A decomposition theory for matroids. I: General results
Recommended article: Q3220598
Recommended article: A decomposition theory for matroids. III. Decomposition conditions
Recommended article: A decomposition theory for matroids. IV: Decomposition of graphs
Recommended article: A decomposition theory for matroids. VII: Analysis of minimal violation matrices
Recommended article: A decomposition theory for matroids. VI: Almost regular matroids
Recommended article: A decomposition theory for matroids. II. Minimal violation matroids
Recommended article: Q3149636
Recommended article: Q4031884
Recommended article: A unique factorization theorem for matroids
description: scientific article; zbMATH DE number 4053634