{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T20:38:40Z","timestamp":1760819920367},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_15","type":"book-chapter","created":{"date-parts":[[2006,11,27]],"date-time":"2006-11-27T23:48:02Z","timestamp":1164671282000},"page":"139-151","source":"Crossref","is-referenced-by-count":13,"title":["Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems"],"prefix":"10.1007","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L., Kantor, W.M., Luks, E.M.: Computational Complexity and the Classification of Finite Simple Groups. In: Proceedings of FOCS 1983, pp. 162\u2013171 (1983)","DOI":"10.1109\/SFCS.1983.10"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/11537311_18","volume-title":"Fundamentals of Computation Theory","author":"V. Bonifaci","year":"2005","unstructured":"Bonifaci, V., Di Iorio, U., Laura, L.: On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 197\u2013208. Springer, Heidelberg (2005)"},{"issue":"6","key":"15_CR3","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J.M. Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating Maximal Independent Sets with Applications to Graph Colouring. Operations Research Letters\u00a032(6), 547\u2013556 (2004)","journal-title":"Operations Research Letters"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K. Cameron","year":"1989","unstructured":"Cameron, K.: Induced Matchings. Discrete Applied Mathematics\u00a024, 97\u2013102 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR5","unstructured":"Cardoso, D.M., Kaminski, M., Lozin, V.: Maximum k-Regular Induced Subgraphs. Rutcor Research Report (RRR) 3 (2006)"},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/11847250_17","volume-title":"Parameterized and Exact Computation","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V.: Finding a Minimum Feedback Vertex Set in Time $\\mathcal{O} (1.7548^n)$ . In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 184\u2013191. Springer, Heidelberg (2006)"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and Conquer: A Simple O(20.288n ) Independent Set Algorithm. In: Proceedings of SODA 2006, pp. 18\u201325 (2006)","DOI":"10.1145\/1109557.1109560"},{"key":"15_CR8","first-page":"47","volume":"87","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the EATCS\u00a087, 47\u201377 (2005)","journal-title":"Bulletin of the EATCS"},{"key":"15_CR9","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"key":"15_CR10","first-page":"127","volume":"76","author":"J.P. Georges","year":"1990","unstructured":"Georges, J.P., Halsey, M.D., Sanaulla, A.M., Whittlesey, M.A.: Edge Domination and Graph Structure. Cong. Numer.\u00a076, 127\u2013144 (1990)","journal-title":"Cong. Numer."},{"issue":"1","key":"15_CR11","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E.M. Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of Graphs of Bounded Valence can be Tested in Polynomial Time. Journal of Computer System Sciences\u00a025(1), 42\u201365 (1982)","journal-title":"Journal of Computer System Sciences"},{"key":"15_CR12","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":"15_CR13","doi-asserted-by":"crossref","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. Theory of Computing Systems (to appear)","DOI":"10.1007\/s00224-007-1334-2"},{"key":"15_CR14","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":"15_CR15","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 Set. Journal of Algorithms\u00a07, 425\u2013440 (1986)","journal-title":"Journal of Algorithms"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(93)90590-P","volume":"120","author":"A. Steger","year":"1993","unstructured":"Steger, A., Yu, M.: On Induced Matchings. Discrete Mathematics\u00a0120, 291\u2013295 (1993)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"15_CR17","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"L.J. Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-Completeness of Some Generalizations of the Maximum Matching Problem. Information Processing Letters\u00a015(1), 14\u201319 (1982)","journal-title":"Information Processing Letters"},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G. Woeginger","year":"2003","unstructured":"Woeginger, G.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink!, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:52:43Z","timestamp":1619495563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11944836_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}