Abstract
A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Bixby, “Matroids and operations research”, in: H. Greenburg, F. Murphy and S. Shaw, eds.,Advanced Techniques in the Practice of Operations Research (North-Holland, Amsterdam, 1982) pp. 333–460.
P. Camion, “Characterization of totally unimodular matrices”,Proceedings of the American Mathematical Society 16 (1965) 1068–1073.
Y. Crama, P.L. Hammer and T. Ibaraki, “Strong unimodularity for matrices and hypergraphs,” Preprint, Rutgers University (1985).
F.G. Commoner, “A sufficient condition for a matrix to be totally unimodular”,Networks 3 (1973) 351–365.
A. Ghouila-Houri, “Caracterisation des matrices totallement unimodulaires”,Comptes Rendus de l'Academie des Sciences de Paris 254 (1962) 1192–1193.
A.J. Hoffman and J.B. Kruskal, “Integral boundary points of convex polyhedra,” in: H. Kuhn and A. W. Tucker, eds.,Linear inequalities and Related systems (Princeton University Press, Princeton, N.J., 1956) pp. 223–246.
M. Padberg, “Total unimodularity and the Euler subgraph problem,”Operations Research Letters, to appear.
P.D. Seymour, “Decomposition of regular matroids,”Journal of Combinatorial Theory B 28 (1980) 305–359.
A. Tamir, Private communication.
A. Tamir, “Totally balanced and totally unimodular matrices defined by center location problems”Discrete Applied Mathematics, to appear.
W. Tutte, “Lectures on matroids”,Journal of National Bureau of Standards 69B (1964) 1–72.
D. Welsh,Matroid Theory (Academic Press, London, 1976).
M. Yannakakis, “On a class of totally unimodular matrices,”Mathematics of Operations Research 10(2) (1985) 280–304.
Author information
Authors and Affiliations
Additional information
Partially supported by a New York University Research Challenge Fund Grant.
Rights and permissions
About this article
Cite this article
Conforti, M., Rao, M.R. Structural properties and recognition of restricted and strongly unimodular matrices. Mathematical Programming 38, 17–27 (1987). https://doi.org/10.1007/BF02591849
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02591849