{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:18Z","timestamp":1759638498866,"version":"3.37.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_14","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T02:57:26Z","timestamp":1384829846000},"page":"150-162","source":"Crossref","is-referenced-by-count":4,"title":["Faster Exact Algorithms for Some Terminal Set Problems"],"prefix":"10.1007","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-642-25591-5_13","volume-title":"Algorithms and Computation","author":"R. Belmonte","year":"2011","unstructured":"Belmonte, R., Golovach, P.A., Heggernes, P., van \u2019t Hof, P., Kami\u0144ski, M., Paulusma, D.: Finding contractions and induced minors in chordal graphs via disjoint paths. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 110\u2013119. Springer, Heidelberg (2011)"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-13731-0_10","volume-title":"Algorithm Theory - SWAT 2010","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"issue":"7","key":"14_CR3","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"40","key":"14_CR4","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science\u00a0411(40), 3736\u20133756 (2010)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"14_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. Algorithmica\u00a055(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"14_CR6","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"D. Corneil","year":"1988","unstructured":"Corneil, D., Fonlupt, J.: The complexity of generalized clique covering. Discrete Applied Mathematics\u00a022(2), 109\u2013118 (1988\u20131989)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J., Wojtaszczyk, J.: Solving connectivity problems parameterized by treewidth in single exponential time. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-28050-4_1","volume-title":"Parameterized and Exact Computation","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 1\u201312. Springer, Heidelberg (2012)"},{"issue":"2","key":"14_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica\u00a052(2), 293\u2013307 (2008)","journal-title":"Algorithmica"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-642-22300-6_34","volume-title":"Algorithms and Data Structures","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating minimal subset feedback vertex sets. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 399\u2013410. Springer, Heidelberg (2011)"},{"key":"14_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer-Verlag New York, Inc., New York (2010)","edition":"1"},{"key":"14_CR12","unstructured":"Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS), vol.\u00a05, pp. 383\u2013394. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2010)"},{"key":"14_CR13","unstructured":"Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: STACS, vol.\u00a05, pp. 383\u2013394 (2010)"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-58201-0_92","volume-title":"Automata, Languages, and Programming","author":"N. Garg","year":"1994","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Multiway Cuts in Directed and Node Weighted Graphs. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 487\u2013498. Springer, Heidelberg (1994)"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-33293-7_10","volume-title":"Parameterized and Exact Computation","author":"P.A. Golovach","year":"2012","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: An exact algorithm for subset feedback vertex set on chordal graphs. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol.\u00a07535, pp. 85\u201396. Springer, Heidelberg (2012)"},{"issue":"4","key":"14_CR16","doi-asserted-by":"publisher","first-page":"1758","DOI":"10.1137\/09077850X","volume":"26","author":"S. Gupta","year":"2012","unstructured":"Gupta, S., Raman, V., Saurabh, S.: Maximum r-regular induced subgraph problem: Fast exponential algorithms and combinatorial bounds. SIAM J. Discrete Math.\u00a026(4), 1758\u20131780 (2012)","journal-title":"SIAM J. Discrete Math."},{"issue":"10","key":"14_CR17","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1016\/j.dam.2007.10.006","volume":"156","author":"D. Kratsch","year":"2008","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback vertex set on at-free graphs. Discrete Applied Mathematics\u00a0156(10), 1936\u20131947 (2008)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"14_CR18","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF01226465","volume":"31","author":"W Mader","year":"1978","unstructured":"Mader, W.: \u00dcber die Maximalzahl kreuzungsfreier H-Wege. Arch. Math (Basel)\u00a031(4), 387\u2013402 (1978\/1979), \n                  \n                    http:\/\/dx.doi.org\/10.1007\/BF01226465","journal-title":"Arch. Math (Basel)"},{"issue":"3","key":"14_CR19","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized Graph Separation Problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1007\/978-3-540-92182-0_73","volume-title":"Algorithms and Computation","author":"S. Mishra","year":"2008","unstructured":"Mishra, S., Raman, V., Saurabh, S., Sikdar, S.: K\u00f6nig deletion sets and vertex covers above the matching size. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 836\u2013847. Springer, Heidelberg (2008)"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-33293-7_3","volume-title":"Parameterized and Exact Computation","author":"M. Pilipczuk","year":"2012","unstructured":"Pilipczuk, M., Pilipczuk, M.: Finding a maximum induced degenerate subgraph faster than 2 n. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol.\u00a07535, pp. 3\u201312. Springer, Heidelberg (2012)"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11785293_17","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"I. Razgon","year":"2006","unstructured":"Razgon, I.: Exact computation of maximum induced forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 160\u2013171. Springer, Heidelberg (2006)"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Razgon, I.: Computing Minimum Directed Feedback Vertex Set in O\n                        *(1.9977\n                  n\n                ). In: ICTCS, pp. 70\u201381 (2007)","DOI":"10.1142\/9789812770998_0010"},{"issue":"3","key":"14_CR24","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms\u00a07(3), 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"14_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters\u00a024(2), 133\u2013137 (1987)","journal-title":"Information Processing Letters"}],"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-319-03898-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T06:41:13Z","timestamp":1558680073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}