{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T10:12:25Z","timestamp":1742379145549},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_69","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"779-790","source":"Crossref","is-referenced-by-count":21,"title":["Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs"],"prefix":"10.1007","author":[{"given":"Anne","family":"Bergeron","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabien","family":"de Montgolfier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Raffinot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"69_CR1","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-32290-0_1","volume-title":"Comparative Genomics","author":"S. B\u00e9rard","year":"2005","unstructured":"B\u00e9rard, S., Bergeron, A., Chauve, C.: Conserved structures in evolution scenarios. In: Lagergren, J. (ed.) RECOMB-WS 2004. LNCS (LNBI), vol.\u00a03388, pp. 1\u201315. Springer, Heidelberg (2005)"},{"key":"69_CR2","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1007\/11561071_69"},{"key":"69_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"S. Booth","year":"1976","unstructured":"Booth, S., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"69_CR4","unstructured":"Bui Xuan, B.M., Habib, M., Paul, C.: From Permutations to Graph Algorithms, LIRMM technical report RR-05021 (2005)"},{"key":"69_CR5","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1109\/ISTCS.1997.595165","volume-title":"Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997","author":"C. Capelle","year":"1997","unstructured":"Capelle, C., Habib, M.: Graph decompositions and factorizing permutations. In: Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, pp. 132\u2013143. IEEE Computer Society Press, Los Alamitos (1997)"},{"key":"69_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in Algebra and Programming - CAAP \u201994","author":"A. Cournier","year":"1994","unstructured":"Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol.\u00a0787, pp. 68\u201384. Springer, Heidelberg (1994)"},{"issue":"2","key":"69_CR7","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1006\/jagm.2001.1185","volume":"41","author":"E. Dahlhaus","year":"2001","unstructured":"Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical algorithms for sequential modular decomposition. J. Algorithms\u00a041(2), 360\u2013387 (2001)","journal-title":"J. Algorithms"},{"key":"69_CR8","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-540-30219-3_3","volume-title":"Algorithms in Bioinformatics","author":"M. Figeac","year":"2004","unstructured":"Figeac, M., Varr\u00e9, J.-S.: Sorting by reversals with common intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.\u00a03240, pp. 26\u201337. Springer, Heidelberg (2004)"},{"key":"69_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-540-27810-8_17","volume-title":"Algorithm Theory - SWAT 2004","author":"M. Habib","year":"2004","unstructured":"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.\u00a03111, pp. 187\u2013198. Springer, Heidelberg (2004)"},{"key":"69_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-48194-X_19","volume-title":"Combinatorial Pattern Matching","author":"S. Heber","year":"2001","unstructured":"Heber, S., Stoye, J.: Finding all common intervals of k permutations. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 207\u2013218. Springer, Heidelberg (2001)"},{"key":"69_CR11","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Parida, L., Weimann, O.: Gene Proximity Analysis Across Whole Genomes via PQ Trees. In: 6th Combinatorial Pattern Matching Conference, CPM (2005)","DOI":"10.1089\/cmb.2005.12.1289"},{"key":"69_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/11604686_37","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"R.M. McConnell","year":"2005","unstructured":"McConnell, R.M., de Montgolfier, F.: Algebraic Operations on PQ-trees and Modular Decomposition Trees. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 421\u2013432. Springer, Heidelberg (2005)"},{"key":"69_CR13","unstructured":"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\u2013545. ACM\/SIAM (1994)"},{"key":"69_CR14","first-page":"45","volume":"4","author":"R.M. McConnell","year":"2000","unstructured":"McConnell, R.M., Spinrad, J.: Ordered vertex partitioning. Discrete Mathematics & Theoretical Computer Science\u00a04, 45\u201360 (2000)","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"69_CR15","first-page":"257","volume":"19","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J.: Substitution decomposition for discrete structures and connections with combinatorial optimization. Annals of Discrete Mathematics\u00a019, 257\u2013356 (1984)","journal-title":"Annals of Discrete Mathematics"},{"issue":"2","key":"69_CR16","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/s004539910014","volume":"26","author":"T. Uno","year":"2000","unstructured":"Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica\u00a026(2), 290\u2013309 (2000)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_69","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T00:25:52Z","timestamp":1683246352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11561071_69","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}