Abstract
Let \({\cal C}\) be a finite set of n elements and \({\cal R}=\{r_1,r_2, \ldots , r_m\}\) a family of m subsets of \({\cal C}\). The family \({\cal R}\) verifies the consecutive ones property if there exists a permutation P of \({\cal C}\) such that each r i in \({\cal R}\) is an interval of P. Several algorithms have been proposed to test this property in time \(O(\sum_{i=1}^m |r_i|)\), all being involved. We present a simpler algorithm, based on a new partitioning scheme.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blin, G., Rizzi, R., Vialette, S.: A faster algorithm for finding minimum tucker submatrices. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 69–77. Springer, Heidelberg (2010)
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones properties, interval graphs and graph planarity using pq-tree algorithm. J. Comput. Syst. Sci. 13, 335–379 (1976)
Charbit, P., Habib, M., Limouzy, V., de Montgolfier, F., Raffinot, M., Rao, M.: A note on computing set overlap classes. Information Processing Letters 108(4), 186–191 (2008)
Chauve, C., Tannier, E.: A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Comput. Biol. 4(11), 11 (2008)
Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. J. Algorithms 36(2), 205–240 (2000)
Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science 234, 59–84 (2000)
Haeupler, B., Tarjan, R.E.: Planarity algorithms via pq-trees (extended abstract). Electronic Notes in Discrete Mathematics 31, 143–149 (2008)
Hsu, W.-L.: A simple test for the consecutive ones property. J. Algorithms 43(1), 1–16 (2002)
Hsu, W.-L., McConnell, R.M.: PC-trees and circular-ones arrangements. Theoretical Computer Science 296, 99–116 (2003)
McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: SODA, pp. 768–777 (2004)
Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. World Scientific, Singapore (2004)
Raffinot, M.: Consecutive ones property testing: cut or swap. CoRR, abs/1008.3786 (2010)
Young, S.: Implementation of PQ-tree Algorithms. Master’s thesis, University of Washington (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Raffinot, M. (2011). Consecutive Ones Property Testing: Cut or Swap. In: Löwe, B., Normann, D., Soskov, I., Soskova, A. (eds) Models of Computation in Context. CiE 2011. Lecture Notes in Computer Science, vol 6735. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21875-0_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-21875-0_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21874-3
Online ISBN: 978-3-642-21875-0
eBook Packages: Computer ScienceComputer Science (R0)