{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:35Z","timestamp":1759638035620},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_3","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T06:50:58Z","timestamp":1346223058000},"page":"3-12","source":"Crossref","is-referenced-by-count":13,"title":["Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n"],"prefix":"10.1007","author":[{"given":"Marcin","family":"Pilipczuk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"3_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM\u00a056(5), 1\u201332 (2009)","journal-title":"J. ACM"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-642-04128-0_50","volume-title":"Algorithms - ESA 2009","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/Exclusion Meets Measure and Conquer. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 554\u2013565. Springer, Heidelberg (2009)"},{"issue":"40-42","key":"3_CR3","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci.\u00a0411(40-42), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 173\u2013182. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-642-23719-5_25","volume-title":"Algorithms \u2013 ESA 2011","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Exact Algorithm for the Maximum Induced Planar Subgraph Problem. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 287\u2013298. Springer, Heidelberg (2011)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-23719-5_26","volume-title":"Algorithms \u2013 ESA 2011","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Scheduling Partially Ordered Jobs Faster Than\u00a0 2\n                  n\n                . In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 299\u2013310. Springer, Heidelberg (2011)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-13731-0_8","volume-title":"Algorithm Theory - SWAT 2010","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated Domination Faster Than O(2\n                  n\n                ). In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 74\u201380. Springer, Heidelberg (2010)"},{"issue":"3","key":"3_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.jda.2011.03.002","volume":"9","author":"D. Binkele-Raible","year":"2011","unstructured":"Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the 2\n                  n\n                -barrier for irredundance: Two lines of attack. J. Discrete Algorithms\u00a09(3), 214\u2013230 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-29344-3_17","volume-title":"LATIN 2012: Theoretical Informatics","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2\n                  n\n                . In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 195\u2013206. Springer, Heidelberg (2012)"},{"key":"3_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":"3_CR11","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)"},{"issue":"2","key":"3_CR12","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"},{"issue":"2","key":"3_CR13","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The Complexity of Satisfiability of Small Depth Circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 75\u201385. Springer, Heidelberg (2009)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) FOCS, pp. 150\u2013159. IEEE (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1065\u20131075 (2010)","DOI":"10.1137\/1.9781611973075.86"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNFSAT. CoRR abs\/1112.2275 (2011)","DOI":"10.1109\/CCC.2012.36"},{"key":"3_CR19","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 r-Regular Induced Subgraph Problems. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol.\u00a04337, pp. 139\u2013151. Springer, Heidelberg (2006)"},{"key":"3_CR20","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":"3_CR21","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)"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-540-92248-3_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Gaspers","year":"2008","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: On Independent Sets and Bicliques in Graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 171\u2013182. Springer, Heidelberg (2008)"},{"key":"3_CR23","unstructured":"Gaspers, S.: Exponential Time Algorithms: Structures, Measures, and Bounds. PhD Thesis, University of Bergen (2008)"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-16926-7_15","volume-title":"Graph Theoretic Concepts in Computer Science","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 147\u2013158. Springer, Heidelberg (2010)"},{"issue":"4","key":"3_CR25","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02579141","volume":"4","author":"A.V. Kostochka","year":"1984","unstructured":"Kostochka, A.V.: Lower bound of the hadwiger number of graphs by their average degree. Combinatorica\u00a04(4), 307\u2013316 (1984)","journal-title":"Combinatorica"},{"issue":"2","key":"3_CR26","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1017\/S0305004100061521","volume":"95","author":"A. Thomason","year":"1984","unstructured":"Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc.\u00a095(2), 261\u2013265 (1984)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"2","key":"3_CR27","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1006\/jctb.2000.2013","volume":"81","author":"A. Thomason","year":"2001","unstructured":"Thomason, A.: The extremal function for complete minors. J. Comb. Theory, Ser. B\u00a081(2), 318\u2013338 (2001)","journal-title":"J. Comb. Theory, Ser. B"}],"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-642-33293-7_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:03:29Z","timestamp":1620115409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}