{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:57:00Z","timestamp":1725566220544},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230717"},{"type":"electronic","value":"9783540286394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_3","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T20:25:35Z","timestamp":1285014335000},"page":"25-36","source":"Crossref","is-referenced-by-count":0,"title":["Chordless Paths Through Three Vertices"],"prefix":"10.1007","author":[{"given":"Robert","family":"Haas","sequence":"first","affiliation":[]},{"given":"Michael","family":"Hoffmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Bazgan, C.: Sch\u00e9mas d\u2019approximation et complexit\u00e9 param\u00e9tr\u00e9e. Rapport du stage (DEA), Universit\u00e9 Paris Sud (1995)"},{"key":"3_CR2","unstructured":"Berge, C.: F\u00e4rbung von Graphen deren s\u00e4mtliche beziehungsweise deren ungerade Kreise starr sind (Zusammenfassung). Wiss. Z.Martin Luther Univ. HalleWittenberg Math. Naturwiss. Reihe, 114\u2013115 (1961)"},{"issue":"1","key":"3_CR3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: On the complexity of testing for odd holes and induces odd paths. Discrete Math. 90(1), 85\u201392 (1991)","journal-title":"Discrete Math."},{"issue":"1","key":"3_CR4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0012-365X(92)90357-L","volume":"102","author":"D. Bienstock","year":"1992","unstructured":"Bienstock, D.: Corrigendum to: On the complexity of testing for odd holes and induces odd paths. Discrete Math. 102(1), 109 (1992)","journal-title":"Discrete Math."},{"issue":"4\u20135","key":"3_CR5","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Arch. Math. Logic\u00a036(4\u20135), 321\u2013337 (1997)","journal-title":"Arch. Math. Logic"},{"issue":"3","key":"3_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(01)00207-1","volume":"81","author":"M. Cesati","year":"2002","unstructured":"Cesati, M.: Perfect code is W[1]-complete. Inform. Process. Lett.\u00a081(3), 163\u2013168 (2002)","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M. Cesati","year":"2003","unstructured":"Cesati, M.: The Turing way to parameterized complexity. J. Comput. Syst. Sci.\u00a067(4), 654\u2013685 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"3_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Inform. Process. Lett.\u00a064(4), 165\u2013171 (1997)","journal-title":"Inform. Process. Lett."},{"key":"3_CR9","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R.: The strong perfect graph theorem (2003) (manuscript)"},{"key":"3_CR10","unstructured":"Chudnovsky, M., Seymour, P.D.: Recognizing Berge graphs (2003) (manuscript)"},{"key":"3_CR11","unstructured":"Cornu\u00e9Jols, G., Liu, X., Vu\u0161kovi\u0107, K.: A polynomial algorithm for recognizing perfect graphs. In: Proc. 44th Annu. IEEE Sympos. Found. Comput. Sci., pp. 20\u201327 (2003)"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoret. Comput. Sci.\u00a0141, 109\u2013131 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR13","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, Heidelberg (1999)"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/3-540-58140-5_10","volume-title":"Logical Foundations of Computer Science","author":"R.G. Downey","year":"1994","unstructured":"Downey, R.G., Fellows, M.R., Kapron, B., Hallett, M.T., Wareham, H.T.: Parameterized complexity and some problems in logic and linguistics. In: Matiyasevich, Y.V., Nerode, A. (eds.) LFCS 1994. LNCS, vol.\u00a0813, pp. 89\u2013101. Springer, Heidelberg (1994)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: A survey of applications. In: Proc. AMS-IMS-SIAM Joint Summer Research Conf., Providence, RI, pp. 1\u201318 (1989)","DOI":"10.1090\/conm\/089\/1006472"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"M.R. Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems. Algorithmica\u00a013, 266\u2013282 (1995)","journal-title":"Algorithmica"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canad. J. Math.\u00a08, 399\u2013404 (1956)","journal-title":"Canad. J. Math."},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci.\u00a010, 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR19","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. W. H. Freeman, New York (1979)"},{"key":"3_CR20","unstructured":"Haas, R.: Service Deployment in Programmable Networks. PhD thesis, ETH Zurich, Switzerland (2003)"},{"key":"3_CR21","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\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"G.S. Lueker","year":"1976","unstructured":"Lueker, G.S., Rose, D.J., Tarjan, R.E.: Algorithmic aspects of vertex elimination in graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Mcdiarmid, C., Reed, B., Schrijver, A., Shepherd, B.: Non-interfering network flows. In: Proc. 3rd Scand. Workshop Algorithm Theory, pp. 245\u2013257 (1992)","DOI":"10.1007\/3-540-55706-7_21"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1006\/jctb.1994.1011","volume":"60","author":"C. Mcdiarmid","year":"1994","unstructured":"Mcdiarmid, C., Reed, B., Schrijver, A., Shepherd, B.: Induced circuits in planar graphs. J. Combin. Theory Ser. B\u00a060, 169\u2013176 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"3_CR25","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Habilitation thesis, Wilhelm-Schickard Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, Germany (2002)"},{"key":"3_CR26","unstructured":"Nikolopoulos, S.D., Palios, L.: Hole and antihole detection in graphs. In: Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pp. 843\u2013852 (2004)"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII. The disjoint paths problem. J. Combin. Theory Ser. B\u00a063, 65\u2013110 (1995)","journal-title":"The disjoint paths problem. J. Combin. Theory Ser. B"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28639-4_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:29:59Z","timestamp":1620012599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}