{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:21:00Z","timestamp":1725603660892},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_25","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"287-298","source":"Crossref","is-referenced-by-count":12,"title":["Exact Algorithm for the Maximum Induced Planar Subgraph Problem"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/11754602_4","volume-title":"Recent Advances in Constraints","author":"O. Angelsmark","year":"2006","unstructured":"Angelsmark, O., Thapper, J.: Partitioning based algorithms for some colouring problems. In: Hnich, B., Carlsson, M., Fages, F., Rossi, F. (eds.) CSCLP 2005. LNCS (LNAI), vol.\u00a03978, pp. 44\u201358. Springer, Heidelberg (2006)"},{"issue":"1-3","key":"25_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0012-365X(03)00230-9","volume":"273","author":"V. Bouchitt\u00e9","year":"2003","unstructured":"Bouchitt\u00e9, V., Mazoit, F., Todinca, I.: Chordal embeddings of planar graphs. Discr. Math.\u00a0273(1-3), 85\u2013102 (2003)","journal-title":"Discr. Math."},{"issue":"1","key":"25_CR3","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput.\u00a031(1), 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discr. Math.\u00a09, 205\u2013212 (1974)","journal-title":"Discr. Math."},{"issue":"3","key":"25_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl.\u00a03(3), 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. In: An EATCS Series: Texts in Theoretical Computer Science, Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput.\u00a038(3), 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"25_CR8","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":"25_CR9","unstructured":"Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: Marion, J.-Y., Schwentick, T. (eds.) STACS. LIPIcs, vol.\u00a05, pp. 383\u2013394. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Gapers, S., Kratch, D., Liedloff, M.: On independent sets and bicliques in graphs. WG (2008); to appear. Preliminary version in WG","DOI":"10.1007\/978-3-540-92248-3_16"},{"key":"25_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completness. Freeman, New York (1979)"},{"key":"25_CR12","unstructured":"Gaspers, S.: Exponential Time Algorithms: Structures, Measures, and Bounds. Phd thesis, University of Bergen (2008)"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of a path in a tree are exactly the chordal graphs. Journal of Combinatorial Theory\u00a016, 47\u201356 (1974)","journal-title":"Journal of Combinatorial Theory"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/11944836_15","volume-title":"FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science","author":"S. Gupta","year":"2006","unstructured":"Gupta, S., Raman, V., Saurabh, S.: Fast exponential algorithms for maximum -regular induced subgraph problems. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol.\u00a04337, pp. 139\u2013151. Springer, Heidelberg (2006)"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0012-365X(72)90041-6","volume":"1","author":"G. Kreweras","year":"1972","unstructured":"Kreweras, G.: Sur les partition non crois\u00e9es d\u2019un circle. Discr. Math.\u00a01, 333\u2013350 (1972)","journal-title":"Discr. Math."},{"issue":"2","key":"25_CR16","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci.\u00a020(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Liebers, A.: Planarizing graphs - a survey and annotated bibliography. Journal of Graph Algorithms and Applications\u00a05 (2001)","DOI":"10.7155\/jgaa.00032"},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel Journal of Mathematics\u00a03, 23\u201328 (1965)","journal-title":"Israel Journal of Mathematics"},{"key":"25_CR19","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":"25_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graphs minors. II. Algorithmic aspects of tree-width. J. of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T03:15:55Z","timestamp":1638414955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}