No label defined (Q3972037)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 15401
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 15401 |
Statements
25 June 1992
0 references
\(pq\)-trees
0 references
binary matrix
0 references
consecutive ones property
0 references
adjacency matrix
0 references
0.8282349109649658
0 references
0.8282349109649658
0 references
0.8155720829963684
0 references
0.7727824449539185
0 references
[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.
0 references
