An extension of a theorem of Fulkerson and Gross
type: Item
instance of: scholarly article
title: An extension of a theorem of Fulkerson and Gross
zbMATH Open document ID: 0862.15012
DOI: 10.1016/0024-3795(94)00308-4
author: R. Chandrasekaran
author: Santosh N. Kabadi
author: Sambhavi Lakshminarayanan
published in: Linear Algebra and its Applications
publication date: 1996-12-01T00:00:00Z
review text: This paper is concerned with a generalization of the consecutive ones property for 0-1 matrices, introduced by \textit{D. R. Fulkerson} and \textit{O. A. Gross} [Pac. J. Math. 105, 835-855 (1965; Zbl 0132.21001)]. This property assures that the matrix is totally unimodular and hence is of importance in integer programming. The property was later generalized to the circular ones property and to the one drop property. The paper answers affirmatively the question whether there is a hierarchy of such properties and corresponding theorems.
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 951788
zbMATH Keywords: unimodular matrix
zbMATH Keywords: consecutive ones property
zbMATH Keywords: 0-1 matrices
zbMATH Keywords: integer programming
reviewed by: Giacomo Bonanno
MaRDI profile type: Publication
full work available at URL: 0024-3795(94)00308-4
OpenAlex ID: W2057030072
cites work: Cyclic Scheduling via Integer Programs with Circular Ones
cites work: Q3346090
cites work: Incidence matrices and interval graphs
cites work: Matrix characterizations of circular-arc graphs
description: scientific article; zbMATH DE number 951788