scientific article; zbMATH DE number 15401

MaRDI QIDQ3972037zbMATH OpenFDO

Authors M. Cozzens, N. V. R. Mahadev

Publication date 25 June 1992

zbMATH Keywords

\(pq\)-treesadjacency matrixbinary matrixconsecutive ones property

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory (05C90)

Review text

[For the entire collection see Zbl 0699.00018.] A binary matrix is said to have the consecutive ones property for columns if its rows can be permuted in such a way that 1's in each column occur consecutively. In the paper is introduced a linear algorithm based on P-Q tree data structure for recognizing the above property of a binary matrix. A generalization of the above notion is a mixed diagonal consecutive ones graph (MCD-graph) whose adjacency matrix with some assignment of zeros and ones to the diagonal elements has the consecutive ones property for columns. Some necessary conditions for MCD-graphs, a linear time algorithm for recognition and some applications are given.

Recommendations

• scientific article; zbMATH DE number 5606342
• On the consecutive ones property
• On testing consecutive-ones property in parallel
• A Simple Test for the Consecutive Ones Property
• Polyhedral aspects of the consecutive ones problem

Cited in

(4)

• Characterizations of two classes of digraphs
• A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix
• A note on consecutive ones in a binary matrix
• A certifying algorithm for the consecutive-ones property

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972037)