{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:00Z","timestamp":1771036380142,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,11,19]],"date-time":"2011-11-19T00:00:00Z","timestamp":1321660800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s00453-011-9588-0","type":"journal-article","created":{"date-parts":[[2011,11,18]],"date-time":"2011-11-18T10:53:38Z","timestamp":1321613618000},"page":"275-316","source":"Crossref","is-referenced-by-count":9,"title":["Cleaning Interval Graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,19]]},"reference":[{"issue":"4","key":"9588_CR1","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H.L. Bodlaender","year":"1990","unstructured":"Bodlaender, H.L.: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms 11(4), 631\u2013643 (1990)","journal-title":"J. Algorithms"},{"key":"9588_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"9588_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/11847250_22","volume-title":"IWPEC 2006: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: A new method for solving fixed-cardinality optimization problems. In: IWPEC 2006: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation. Lecture Notes in Computer Science, vol. 4169, pp. 239\u2013250. Springer, Berlin (2006)"},{"key":"9588_CR4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"C.J. Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11, 13\u201321 (1981)","journal-title":"Networks"},{"issue":"1","key":"9588_CR5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1137\/0210015","volume":"10","author":"C.J. Colbourn","year":"1981","unstructured":"Colbourn, C.J., Booth, K.S.: Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10(1), 203\u2013225 (1981)","journal-title":"SIAM J. Comput."},{"key":"9588_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/11672142_29","volume-title":"STACS 2006: Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science","author":"J. D\u00edaz","year":"2006","unstructured":"D\u00edaz, J., Thilikos, D.M.: Fast FPT-algorithms for cleaning grids. In: STACS 2006: Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 3884, pp. 361\u2013371. Springer, Berlin (2006)"},{"issue":"3","key":"9588_CR7","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0020-0190(99)00054-X","volume":"70","author":"Y. Dinitz","year":"1999","unstructured":"Dinitz, Y., Itai, A., Rodeh, M.: On an algorithm of Zemlyachenko for subtree isomorphism. Inf. Process. Lett. 70(3), 141\u2013146 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9588_CR8","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"issue":"3","key":"9588_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"9588_CR10","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/800141.804671","volume-title":"STOC 1980: Proceedings of the 12th Annual ACM Symposium on Theory of Computing","author":"I.S. Filotti","year":"1980","unstructured":"Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus (working paper). In: STOC 1980: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 236\u2013243. ACM, New York (1980)"},{"key":"9588_CR11","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, New York (2006)"},{"key":"9588_CR12","series-title":"Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. Freeman, New York (1979)"},{"key":"9588_CR13","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P.C. Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964)","journal-title":"Can. J. Math."},{"issue":"5","key":"9588_CR14","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1016\/j.jcss.2007.01.003","volume":"73","author":"M. Hajiaghayi","year":"2007","unstructured":"Hajiaghayi, M., Nishimura, N.: Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. J. Comput. Syst. Sci. 73(5), 755\u2013768 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9588_CR15","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0304-3975(89)90011-X","volume":"63","author":"A. Lingas","year":"1989","unstructured":"Lingas, A.: Subgraph isomorphism for biconnected outerplanar graphs in cubic time. Theor. Comput. Sci. 63(3), 295\u2013302 (1989)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9588_CR16","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G.S. Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A linear time algorithm for deciding interval graph isomorphism. J. ACM 26(2), 183\u2013195 (1979)","journal-title":"J. ACM"},{"issue":"1","key":"9588_CR17","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E.M. Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"15","key":"9588_CR18","doi-asserted-by":"crossref","first-page":"3258","DOI":"10.1016\/j.dam.2009.06.022","volume":"157","author":"D. Marx","year":"2009","unstructured":"Marx, D., Schlotter, I.: Parameterized graph cleaning problems. Discrete Appl. Math. 157(15), 3258\u20133267 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9588_CR19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D.W. Matula","year":"1978","unstructured":"Matula, D.W.: Subtree isomorphism in O(n 5\/2). Ann. Discrete Math. 2, 91\u2013106 (1978)","journal-title":"Ann. Discrete Math."},{"key":"9588_CR20","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/800141.804670","volume-title":"STOC 1980: Proceedings of the 12th Annual ACM Symposium on Theory of Computing","author":"G.L. Miller","year":"1980","unstructured":"Miller, G.L.: Isomorphism testing for graphs of bounded genus. In: STOC 1980: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pp. 225\u2013235. ACM, New York (1980)"},{"key":"9588_CR21","volume-title":"Proc. Seminar on Comb. Anal. at Moscow State University","author":"V.N. Zemlyachenko","year":"1970","unstructured":"Zemlyachenko, V.N.: Canonical numbering of trees. In: Proc. Seminar on Comb. Anal. at Moscow State University (1970). (In Russian)"},{"key":"9588_CR22","unstructured":"Zemlyachenko, V.N.: Determining tree isomorphism. In: Voprosy Kibernetiki, Proc. of the Seminar on Combinatorial Mathematics, Moscow, 1971, pp.\u00a054\u201360. Akad. Nauk SSSR, Scientific Council on the Complex Problem \u201cCybernetics\u201d, 1973. (In Russian)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9588-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9588-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9588-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:08Z","timestamp":1559123108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9588-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,19]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["9588"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9588-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,19]]}}}