{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T19:20:48Z","timestamp":1779304848692,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,3,1]],"date-time":"1995-03-01T00:00:00Z","timestamp":794016000000},"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":[[1995,3]]},"DOI":"10.1007\/bf01190507","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T07:00:56Z","timestamp":1108710056000},"page":"266-282","source":"Crossref","is-referenced-by-count":57,"title":["The complexity of induced minors and related problems"],"prefix":"10.1007","volume":"13","author":[{"given":"M. R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Kratochvil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Middendorf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Pfeiffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., A linear time algorithm for finding tree-decompositions of small treewidth,Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 226?234.","DOI":"10.1145\/167088.167161"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K. Cameron","year":"1989","unstructured":"Cameron, K., Induced matchings,Discrete Appl. Math. 24 (1989), 97?102.","journal-title":"Discrete Appl. Math."},{"key":"CR3","unstructured":"Courcelle, B., The monadic second-order logic of graphs, I: Recognizable sets of finite graphs,Inform. and Control (to appear)."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J., Maximum matching and a polyhedron with 0, 1 vertices,J. Res. Nat. Bur. Standards 69B (1965), 125?130.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/089\/1006472","volume":"89","author":"M. R. Fellows","year":"1989","unstructured":"Fellows, M. R., The Robertson-Seymour theorems: A survey of applications,Contemp. Math. 89 (1989), 1?18.","journal-title":"Contemp. Math."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J. E., and Wyllie, J., The directed subgraph homeomorphism problem,J. Theoret. Comput. Sci. 10 (1980), 111?121.","journal-title":"J. Theoret. Comput. Sci."},{"key":"CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., and Johnson, D. S.,Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York, 1979."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. M. Karp","year":"1975","unstructured":"Karp, R. M., On the complexity of combinatorial problems,Networks 5 (1975), 45?68.","journal-title":"Networks"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/0404022","volume":"4","author":"J. Kratochvil","year":"1991","unstructured":"Kratochvil, J., Lubiw, A., and Ne?et?il, J., Noncrossing subgraphs in topological layouts,SIAM J. Discrete Math. 4 (1991), 223?244.","journal-title":"SIAM J. Discrete Math."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D., Planar formulae and their uses,SIAM J. Comput. 11 (1982), 329?343.","journal-title":"SIAM J. Comput."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(88)90125-4","volume":"22","author":"A. Lubiw","year":"1988\/9","unstructured":"Lubiw, A., A note on odd\/even cycles,Discrete Appl. Math. 22 (1988\/9), 87?92.","journal-title":"Discrete Appl. Math."},{"key":"CR12","first-page":"703","volume":"29","author":"J. Matou?ek","year":"1988","unstructured":"Matou?ek, J., Ne?et?il, J., and Thomas, R., On polynomial time decidability of induced minor closed classes,Comment. Math. Univ. Carolin. 29 (1988), 703?710.","journal-title":"Comment. Math. Univ. Carolin."},{"key":"CR13","unstructured":"McDiarmid, C, Reed, B., Schrijver, A., and Shepherd, B., Induced circuits in planar graphs, Preprint."},{"key":"CR14","unstructured":"McDiarmid, C., Reed, B., Schrijver, A., and Shepherd, B., Non-interfering paths in planar digraphs, Preprint."},{"key":"CR15","unstructured":"Moret, B., Planar not-all-equal 3sat is inP, SIGACT News (1989)."},{"key":"CR16","unstructured":"Robertson, N, and Seymour, P. D., Graph minors I-XVIII."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/BF02574704","volume":"6","author":"A. Schrijver","year":"1991","unstructured":"Schrijver, A., Disjoint homotopic paths and trees in a planar graph,Discrete Comput. Geom. 6 (1991), 527?574.","journal-title":"Discrete Comput. Geom."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"P. D. Seymour","year":"1980","unstructured":"Seymour, P. D., Disjoint paths in graphs,Discrete Math. 29 (1980), 293?309.","journal-title":"Discrete Math."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y. Shiloach","year":"1980","unstructured":"Shiloach, Y., A polynomial solution to the undirected two paths problem,J. Assoc. Comput. Mach. 27 (1980), 445?456.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/0095-8956(85)90069-3","volume":"38","author":"R. Thomas","year":"1985","unstructured":"Thomas, R., Graphs without K4 and well-quasi-ordering,J. Combin. Theory Ser. B 38 (1985), 445?456.","journal-title":"J. Combin. Theory Ser. B"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","volume":"29","author":"C. Thomassen","year":"1980","unstructured":"Thomassen, C., 2-linked graphs,European J. Combin. 29 (1980), 371?378.","journal-title":"European J. Combin."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"L. G. Valiant","year":"1981","unstructured":"Valiant, L. G., Universality considerations in VLSI circuits,IEEE Trans. Comput. 30 (1981), 135?140.","journal-title":"IEEE Trans. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190507.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01190507\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T09:08:17Z","timestamp":1556615297000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01190507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["BF01190507"],"URL":"https:\/\/doi.org\/10.1007\/bf01190507","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}