{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:24Z","timestamp":1759063464851},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_27","type":"book-chapter","created":{"date-parts":[[2010,9,3]],"date-time":"2010-09-03T21:16:57Z","timestamp":1283548617000},"page":"309-321","source":"Crossref","is-referenced-by-count":5,"title":["Feedback Vertex Set and Longest Induced Path on AT-Free Graphs"],"prefix":"10.1007","author":[{"given":"Dieter","family":"Kratsch","sequence":"first","affiliation":[]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics\u00a012, 289\u2013297 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(97)00031-0","volume":"79","author":"H. Bodlaender","year":"1997","unstructured":"Bodlaender, H., Thilikos, D.: Treewidth for graphs with small chordality. Discrete Applied Mathematics\u00a079, 45\u201361 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(87)90128-9","volume":"54","author":"A. Brandst\u00e4dt","year":"1987","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On domination problems for permutation and other graphs. Theoretical Computer Science\u00a054, 181\u2013198 (1987)","journal-title":"Theoretical Computer Science"},{"key":"27_CR4","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique width of bipartite permutation graphs, RRR-29-2001, Rutgers University"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1002\/(SICI)1097-0037(200001)35:1<26::AID-NET3>3.0.CO;2-M","volume":"35","author":"H.J. Broersma","year":"2000","unstructured":"Broersma, H.J., Huck, A., Kloks, T., Koppius, O., Kratsch, D., M\u00fcller, H., Tuinstra, H.: Degreepreserving trees. Networks\u00a035, 26\u201339 (2000)","journal-title":"Networks"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"H.J. Broersma","year":"1999","unstructured":"Broersma, H.J., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent sets in asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics\u00a012, 276\u2013287 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/s00453-001-0091-x","volume":"32","author":"H.J. Broersma","year":"2002","unstructured":"Broersma, H.J., Kloks, T., Kratsch, D., M\u00fcller, H.: A generalization ofAT-free graphs and a generic algorithm for solving triangulation problems. Algorithmica\u00a032, 594\u2013610 (2002)","journal-title":"Algorithmica"},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D.G. Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics\u00a010, 399\u2013430 (1997)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems\u00a033, 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"key":"27_CR10","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1997","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, Heidelberg (1997)"},{"key":"27_CR11","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. Freeman, NewYork (1979)"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0020-0190(01)00222-8","volume":"81","author":"F. Gavril","year":"2002","unstructured":"Gavril, F.: Algorithms for maximum weight induced paths. Information Processing Letters\u00a081, 203\u2013208 (2002)","journal-title":"Information Processing Letters"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BFb0024501","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"K. Kloks","year":"1997","unstructured":"Kloks, K., Kratsch, D., M\u00fcller, H.: Asteroidal sets in graphs. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 229\u2013241. Springer, Heidelberg (1997)"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1006\/jagm.2000.1137","volume":"38","author":"J. Kleinberg","year":"2001","unstructured":"Kleinberg, J., Kumar, A.: Wavelength conversion in optical networks. Journal of Algorithms\u00a038, 25\u201350 (2001)","journal-title":"Journal of Algorithms"},{"key":"27_CR15","unstructured":"K\u00f6hler, E.: Graphs without asteroidal triples, PhD thesis, TU Berlin (1999), ftp:\/\/ftp.math.tu-berlin.de\/pub\/combi\/ekoehler\/diss"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(94)00133-2","volume":"52","author":"D.Y. Liang","year":"1994","unstructured":"Liang, D.Y.: On the feedback vertex set problem in permutation graphs. Information Processing Letters\u00a052, 123\u2013129 (1994)","journal-title":"Information Processing Letters"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"D.Y. Liang","year":"1997","unstructured":"Liang, D.Y., Chang, M.S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica\u00a034, 337\u2013346 (1997)","journal-title":"Acta Informatica"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(96)00193-7","volume":"61","author":"C.L. Lu","year":"1997","unstructured":"Lu, C.L., Tang, C.Y.: A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Information Processing Letters\u00a061, 107\u2013111 (1997)","journal-title":"Information Processing Letters"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Spinrad, J.: Efficient graph representations, American Mathematical Society, Fields Institute Monograph Series 19 (2003)","DOI":"10.1090\/fim\/019"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM Journal on Computing\u00a01, 146\u2013160 (1972)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T09:19:18Z","timestamp":1559553558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}