{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:41:47Z","timestamp":1725522107155},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540922476"},{"type":"electronic","value":"9783540922483"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92248-3_24","type":"book-chapter","created":{"date-parts":[[2008,12,4]],"date-time":"2008-12-04T13:36:17Z","timestamp":1228397777000},"page":"264-274","source":"Crossref","is-referenced-by-count":0,"title":["Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms"],"prefix":"10.1007","author":[{"given":"Athanassios","family":"Koutsonas","sequence":"first","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A. Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artificial Intelligence Res.\u00a012, 219\u2013234 (2000) (electronic)","journal-title":"J. Artificial Intelligence Res."},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/978-3-540-70918-3_28","volume-title":"STACS 2007","author":"H.L. Bodlaender","year":"2007","unstructured":"Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 320\u2013331. Springer, Heidelberg (2007)"},{"key":"24_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Parameterized and Exact Computation","author":"K. Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M., Langston, M., Mac, S., Rosamond, F.: The undirected feedback vertex set problem has a Poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 192\u2013202. Springer, Heidelberg (2006)"},{"key":"24_CR4","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for the feedback vertex set problems. Technical Report 348, Department of Informatics, University of Bergen, Bergen, Norway (2007)"},{"issue":"4-5","key":"24_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"F.A. Chudak","year":"1998","unstructured":"Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett.\u00a022(4-5), 111\u2013118 (1998)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"24_CR6","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM\u00a052(6), 866\u2013893 (2005) (electronic)","journal-title":"J. ACM"},{"issue":"4","key":"24_CR7","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1125-y","volume":"41","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica\u00a041(4), 245\u2013267 (2005)","journal-title":"Algorithmica"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"24_CR9","unstructured":"Dorn, F.: Designing Subexponential Algorithms: Problems, Techniques & Structures. PhD thesis, Department of Informatics, University of Bergen (2007)"},{"issue":"1","key":"24_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.cosrev.2008.02.004","volume":"2","author":"F. Dorn","year":"2008","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential parameterized algorithms. Comp, Sc. Rev.\u00a02(1), 29\u201339 (2008)","journal-title":"Comp, Sc. Rev."},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-540-28629-5_37","volume-title":"Mathematical Foundations of Computer Science 2004","author":"H. Fernau","year":"2004","unstructured":"Fernau, H., Juedes, D.: A geometric approach to parameterized algorithms for domination problems on planar graphs. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 488\u2013499. Springer, Heidelberg (2004)"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-1-4757-3023-4_4","volume-title":"Handbook of combinatorial optimization","author":"P. Festa","year":"1999","unstructured":"Festa, P., Pardalos, P.M., Resende, M.G.C.: Feedback set problems. In: Handbook of combinatorial optimization, vol.\u00a0A (suppl.), pp. 209\u2013258. Kluwer Acad. Publ., Dordrecht (1999)"},{"key":"24_CR13","series-title":"Theoretical Computer Science. EATCS Series","volume-title":"Parameterized complexity theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Theoretical Computer Science. EATCS Series. Springer, Berlin (2006)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica (to appear, 2008)","DOI":"10.1007\/s00453-007-9152-0"},{"issue":"2","key":"24_CR15","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/S0097539702419649","volume":"36","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. SIAM J. Comput.\u00a036(2), 281\u2013309 (2006) (electronic)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"24_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. Journal of Graph Theory\u00a051(1), 53\u201381 (2006)","journal-title":"Journal of Graph Theory"},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/3-540-61310-2_12","volume-title":"Integer Programming and Combinatorial Optimization","author":"M.X. Goemans","year":"1996","unstructured":"Goemans, M.X., Williamson, D.P.: Primal-dual approximation algorithms for feedback problems in planar graphs. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol.\u00a01084, pp. 147\u2013161. Springer, Heidelberg (1996)"},{"issue":"1","key":"24_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/PL00009810","volume":"18","author":"M.X. Goemans","year":"1998","unstructured":"Goemans, M.X., Williamson, D.P.: Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica\u00a018(1), 37\u201359 (1998)","journal-title":"Combinatorica"},{"key":"24_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/11523468_31","volume-title":"Automata, Languages and Programming","author":"Q.-P. Gu","year":"2005","unstructured":"Gu, Q.-P., Tamaki, H.: Optimal branch-decomposition of planar graphs in \n                    \n                      \n                    \n                    $O(n\\sp 3)$\n                   time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-36379-3_25","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"2002","unstructured":"Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint set on plane and planar graphs. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 282\u2013295. Springer, Heidelberg (2002)"},{"issue":"3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1109\/43.833199","volume":"19","author":"H.-M. Lin","year":"2000","unstructured":"Lin, H.-M., Jou, J.-Y.: On computing the minimum feedback vertex set of a directed graph by contraction operations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a019(3), 295\u2013307 (2000)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"24_CR22","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"issue":"2","key":"24_CR23","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertsonand","year":"1991","unstructured":"Robertsonand, N., Seymour, P.D.: Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"24_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"}],"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-92248-3_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T08:34:10Z","timestamp":1551688450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92248-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922476","9783540922483"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92248-3_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}