{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:45Z","timestamp":1759638885394},"reference-count":43,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2014,3,30]],"date-time":"2014-03-30T00:00:00Z","timestamp":1396137600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"DOI":"10.1007\/s00453-014-9877-5","type":"journal-article","created":{"date-parts":[[2014,3,29]],"date-time":"2014-03-29T16:30:19Z","timestamp":1396110619000},"source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs"],"prefix":"10.1007","author":[{"given":"Danny","family":"Hermelin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,3,30]]},"reference":[{"issue":"4","key":"9877_CR1","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"2\u20133","key":"9877_CR2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s10107-005-0649-5","volume":"105","author":"K Cameron","year":"2006","unstructured":"Cameron, K., Hell, P.: Independent packings in structured graphs. Math. Program. 105(2\u20133), 201\u2013213 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"9877_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/jgt.20192","volume":"54","author":"M Chudnovsky","year":"2007","unstructured":"Chudnovsky, M., Ovetsky, A.: Coloring quasi-line graphs. J. Graph Theory 54(1), 41\u201350 (2007)","journal-title":"J. Graph Theory"},{"key":"9877_CR4","first-page":"153","volume":"327","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Seymour, P.D.: The structure of claw-free graphs. Surveys in Comb. 327, 153\u2013171 (2005)","journal-title":"Surveys in Comb."},{"issue":"6","key":"9877_CR5","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1016\/j.jctb.2007.02.002","volume":"97","author":"M Chudnovsky","year":"2007","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. I. Orientable prismatic graphs. J. Comb. Theory Ser. B 97(6), 1373\u20131410 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"9877_CR6","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.jctb.2007.06.006","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. II. Non-orientable prismatic graphs. J. Comb. Theory Ser. B 98(2), 249\u2013290 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"9877_CR7","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1016\/j.jctb.2008.03.001","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. III. Circular interval graphs. J. Comb. Theory Ser. B 98(4), 812\u2013834 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"9877_CR8","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1016\/j.jctb.2007.06.007","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. IV. Decomposition theorem. J. Comb. Theory Ser. B 98(5), 839\u2013938 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"9877_CR9","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1016\/j.jctb.2008.03.002","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. V. Global structure. J. Comb. Theory Ser. B 98(6), 1373\u20131410 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"9877_CR10","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1016\/j.jctb.2010.04.005","volume":"100","author":"M Chudnovsky","year":"2010","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. VI. Coloring. J. Comb. Theory Ser. B 100(6), 560\u2013572 (2010)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"9877_CR11","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1016\/j.jctb.2012.07.005","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M., Seymour, P.D.: Claw-free graph. VII. Quasi-line graphs. J. Comb. Theory Ser. B 102(6), 1267\u20131294 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"50","key":"9877_CR12","doi-asserted-by":"crossref","first-page":"6982","DOI":"10.1016\/j.tcs.2011.09.010","volume":"412","author":"M Cygan","year":"2011","unstructured":"Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50), 6982\u20137000 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9877_CR13","doi-asserted-by":"crossref","unstructured":"Damaschke, P.: Induced subgraph isomorphism for cographs is $${\\sf NP}$$ NP -complete. In: Graph-Theoretic Concepts in Computer Science (WG 1990), Lecture Notes in Computer Science, vol. 484, pp. 72\u201378 (1991)","DOI":"10.1007\/3-540-53832-1_32"},{"key":"9877_CR14","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 68\u201381 (2012)","DOI":"10.1137\/1.9781611973099.6"},{"key":"9877_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"9877_CR16","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: An algorithmic decomposition of claw-free graphs leading to an $$O(n^3)$$ O ( n 3 ) -algorithm for the weighted stable set problem. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 630\u2013646 (2011)","DOI":"10.1137\/1.9781611973082.49"},{"issue":"1\u20133","key":"9877_CR17","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","volume":"164","author":"RJ Faudree","year":"1997","unstructured":"Faudree, R.J., Flandrin, E., Ryj\u00e1cek, Z.: Claw-free graphs: a survey. Discret. Math. 164(1\u20133), 87\u2013147 (1997)","journal-title":"Discret. Math."},{"issue":"1","key":"9877_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9877_CR19","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s00453-007-9146-y","volume":"52","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F.A., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167\u2013176 (2008)","journal-title":"Algorithmica"},{"key":"9877_CR20","volume-title":"Computers and Intractability: A Guide to the Theory of $${\\sf NP}$$ NP","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of $${\\sf NP}$$ NP -Completeness. Freeman, San Francisco (1979)"},{"key":"9877_CR21","doi-asserted-by":"crossref","unstructured":"Golovach, P., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-free graphs. In: Algorithm Theory (SWAT 2012), Lecture Notes in Computer Science, vol. 7357, pp. 153\u2013164 (2012)","DOI":"10.1007\/978-3-642-31155-0_14"},{"key":"9877_CR22","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in claw-free graphs. In: Algorithms (ESA 2012), Lecture Notes in Computer Science, vol. 7501, pp. 515\u2013526 (2012)","DOI":"10.1007\/978-3-642-33090-2_45"},{"key":"9877_CR23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"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. Theor. Comput. Sci. 234, 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9877_CR24","unstructured":"Heggernes, P., van, \u2019t Hof, P., Meister, D., Villanger, Y.: The induced subgraph isomorphism problem on proper interval graphs and bipartite permutation graphs. Preprint (2012)."},{"key":"9877_CR25","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Meister, D., Villanger, Y.: Induced subgraph isomorphism on interval and proper interval graphs. In: Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science, vol. 6507, pp. 399\u2013409 (2010)","DOI":"10.1007\/978-3-642-17514-5_34"},{"key":"9877_CR26","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J.: Parameterized complexity of induced $$H$$ H -matching in claw-free graphs. In: Algorithms (ESA 2012), Lecture Notes in Computer Science, vol. 7501, pp. 624\u2013635 (2012)","DOI":"10.1007\/978-3-642-33090-2_54"},{"key":"9877_CR27","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. In: Automata, Languages and Programming (ICALP 2011), Lecture Notes in Computer Science, vol. 6755, pp. 462\u2013473 (2011)","DOI":"10.1007\/978-3-642-22006-7_39"},{"key":"9877_CR28","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 104\u2013113 (2012)","DOI":"10.1137\/1.9781611973099.9"},{"issue":"3","key":"9877_CR29","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/jgt.20334","volume":"59","author":"AD King","year":"2008","unstructured":"King, A.D., Reed, B.A.: Bounding $$\\chi $$ \u03c7 in terms of $$\\omega $$ \u03c9 and $$\\Delta $$ \u0394 for quasi-line graphs. J. Graph Theory 59(3), 215\u2013228 (2008)","journal-title":"J. Graph Theory"},{"issue":"3","key":"9877_CR30","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"D Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput. 12(3), 601\u2013609 (1983)","journal-title":"SIAM J. Comput."},{"key":"9877_CR31","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science, vol. 4271, pp. 58\u201367 (2006)."},{"issue":"4","key":"9877_CR32","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s00453-003-1035-4","volume":"37","author":"D Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and $$P_{5}$$ P 5 -free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37(4), 327\u2013346 (2003)","journal-title":"Algorithmica"},{"issue":"7\u20138","key":"9877_CR33","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1016\/j.dam.2012.11.005","volume":"161","author":"MC Lin","year":"2013","unstructured":"Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Normal Helly circular-arc graphs and its subclasses. Discret. Appl. Math. 161(7\u20138), 1037\u20131059 (2013)","journal-title":"Discret. Appl. Math."},{"key":"9877_CR34","unstructured":"Maier, D., Storer, J.A.: A note on the complexity of the superstring problem. Technical Report 233, Computer Science Laboratory, Princeton University (1977)."},{"key":"9877_CR35","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Algorithms (ESA 2005), Lecture Notes in Computer Science, vol. 3669, pp. 448\u2013459 (2005)","DOI":"10.1007\/11561071_41"},{"issue":"1\u20133","key":"9877_CR36","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0012-365X(02)00578-2","volume":"263","author":"TA McKee","year":"2003","unstructured":"McKee, T.A.: Restricted circular-arc graphs and clique cycles. Discret. Math. 263(1\u20133), 221\u2013231 (2003)","journal-title":"Discret. Math."},{"key":"9877_CR37","doi-asserted-by":"crossref","unstructured":"Moser, H.: A problem kernelization for graph packing. In: Theory and Practice of Computer Science (SOFSEM 2009), Lecture Notes in Computer Science, vol. 5404, pp. 401\u2013412 (2009)","DOI":"10.1007\/978-3-540-95891-8_37"},{"issue":"2","key":"9877_CR38","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7(2), 181\u2013190 (2009)","journal-title":"J. Discret. Algorithms"},{"issue":"8","key":"9877_CR39","doi-asserted-by":"crossref","first-page":"1426","DOI":"10.1016\/j.disc.2011.12.029","volume":"312","author":"G Oriolo","year":"2012","unstructured":"Oriolo, G., Pietropaoli, U., Stauffer, G.: On the recognition of fuzzy circular interval graphs. Discret. Math. 312(8), 1426\u20131435 (2012)","journal-title":"Discret. Math."},{"issue":"3","key":"9877_CR40","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.tcs.2005.10.009","volume":"351","author":"E Prieto","year":"2006","unstructured":"Prieto, E., Sloper, C.: Looking at the stars. Theor. Comput. Sci. 351(3), 437\u2013445 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9877_CR41","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.: A $$\\max \\{m, n\\}$$ max { m , n } algorithm for determining the graph $$H$$ H from its line graph $$G$$ G . Inf. Process. Lett. 2(4), 108\u2013112 (1973)","journal-title":"Inf. Process. Lett."},{"key":"9877_CR42","doi-asserted-by":"crossref","unstructured":"Spinrad, J.R.: Efficient graph representations, Field Institute Monographs, vol. 19, American Mathematical Society (2003)","DOI":"10.1090\/fim\/019"},{"key":"9877_CR43","doi-asserted-by":"crossref","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Congruent graphs and the connectivity of graphs. American J. Math. 54, 150\u2013168 (1932)","journal-title":"American J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9877-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9877-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9877-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T22:06:54Z","timestamp":1565302014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9877-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,30]]},"references-count":43,"alternative-id":["9877"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9877-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,30]]}}}