Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs

1. Bérard, S., Bergeron, A., Chauve, C.: Conserved structures in evolution scenarios. In: Lagergren, J. (ed.) RECOMB-WS 2004. LNCS (LNBI), vol. 3388, pp. 1–15. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

2. Bergeron, A., Chauve, C., de Montgolfier, F., Raffinot, M.: Computing common intervals of K permutations, with applications to modular decomposition of graphs. LIAFA technical report 2005-006, available at: http://www.liafa.jussieu.fr/web9/rapportrech/listrapport_fr.php?anscol=2005

3. Booth, S., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976)

   Article  MATH  MathSciNet  Google Scholar 

4. Bui Xuan, B.M., Habib, M., Paul, C.: From Permutations to Graph Algorithms, LIRMM technical report RR-05021 (2005)

   Google Scholar 

5. Capelle, C., Habib, M.: Graph decompositions and factorizing permutations. In: Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, pp. 132–143. IEEE Computer Society Press, Los Alamitos (1997)

   Chapter  Google Scholar 

6. Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol. 787, pp. 68–84. Springer, Heidelberg (1994)

   Chapter  Google Scholar 

7. Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical algorithms for sequential modular decomposition. J. Algorithms 41(2), 360–387 (2001)

   Article  MATH  MathSciNet  Google Scholar 

8. Figeac, M., Varré, J.-S.: Sorting by reversals with common intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol. 3240, pp. 26–37. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

9. Habib, M., de Montgolfier, F., Paul, C.: A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 187–198. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

10. Heber, S., Stoye, J.: Finding all common intervals of k permutations. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol. 2089, pp. 207–218. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

11. Landau, G.M., Parida, L., Weimann, O.: Gene Proximity Analysis Across Whole Genomes via PQ Trees. In: 6th Combinatorial Pattern Matching Conference, CPM (2005)

    Google Scholar 

12. McConnell, R.M., de Montgolfier, F.: Algebraic Operations on PQ-trees and Modular Decomposition Trees. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 421–432. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

13. McConnell, R.M., Spinrad, J.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 536–545. ACM/SIAM (1994)

    Google Scholar 

14. McConnell, R.M., Spinrad, J.: Ordered vertex partitioning. Discrete Mathematics & Theoretical Computer Science 4, 45–60 (2000)

    MATH  MathSciNet  Google Scholar 

15. Möhring, R.H., Radermacher, F.J.: Substitution decomposition for discrete structures and connections with combinatorial optimization. Annals of Discrete Mathematics 19, 257–356 (1984)

    Google Scholar 

16. Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica 26(2), 290–309 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references