Journal
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
Volume 43, Issue 1, Pages 1-16Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1006/jagm.2001.1205
Keywords
-
Ask authors/readers for more resources
A (0, 1)-matrix satisfies the consecutive ones property if there exists a column permutation such that the ones in each row of the resulting matrix are consecutive. Booth and Lueker (1976, J. Comput. System Sci. 13, 335-378) designed a linear time-testing algorithm for this property based on a data structure called PQ-trees. This procedure is quite complicated and the linear-time-amortized analysis is also rather involved. We developed an off-line linear time test for the consecutive ones property without using PQ-trees and the corresponding template matching, which makes ours considerably simpler. A simplification of the consecutive ones test will immediately simplify algorithms (and computer codes) for interval-graph and planar-graph recognition. Our approach is based on a decomposition technique that separates the rows into prime subsets, each of which admits essentially a unique column ordering that realizes the consecutive ones property. The success of this approach is based on finding a good row ordering to be tested iteratively. (C) 2002 Elsevier Science (USA).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available