A Simple Test for the Consecutive Ones Property

✍ Scribed by Wen-Lian Hsu

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 170 KB
• Volume: 43
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1205

✦ Synopsis

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 timetesting 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.  2002 Elsevier Science (USA)