{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:27Z","timestamp":1759638987580,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450426"},{"type":"electronic","value":"9783642450433"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45043-3_32","type":"book-chapter","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T14:05:50Z","timestamp":1384265150000},"page":"370-381","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs"],"prefix":"10.1007","author":[{"given":"Neeldhara","family":"Misra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","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":[{"issue":"7","key":"32_CR1","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.dam.2008.08.020","volume":"158","author":"L. Addario-Berry","year":"2010","unstructured":"Addario-Berry, L., Kennedy, W.S., King, A.D., Li, Z., Reed, B.A.: Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph. Discrete Applied Mathematics\u00a0158(7), 765\u2013770 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"issue":"8","key":"32_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR4","unstructured":"Byskov, J.M.: Algorithms for k-colouring and finding maximal independent sets. In: SODA, pp. 456\u2013457 (2003)"},{"issue":"6","key":"32_CR5","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. Oper. Res. Lett.\u00a032(6), 547\u2013556 (2004)","journal-title":"Oper. Res. Lett."},{"key":"32_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-19222-7_1","volume-title":"Combinatorial Algorithms","author":"K. Dabrowski","year":"2011","unstructured":"Dabrowski, K., Lozin, V.V., M\u00fcller, H., Rautenbach, D.: Parameterized algorithms for the independent set problem in some hereditary graph classes. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol.\u00a06460, pp. 1\u20139. Springer, Heidelberg (2011)"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260 (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"32_CR8","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag New York, Inc., Secaucus (2006)"},{"issue":"2","key":"32_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":"32_CR10","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC, pp. 133\u2013142 (2008)","DOI":"10.1145\/1374376.1374398"},{"issue":"1","key":"32_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"issue":"4","key":"32_CR12","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":"3","key":"32_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett.\u00a027(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"32_CR14","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci.\u00a0289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR15","first-page":"55","volume-title":"Selected Topics in Graph Theory","author":"L. Lovasz","year":"1983","unstructured":"Lovasz, L.: Perfect graphs. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, vol.\u00a02, pp. 55\u201367. Academic Press, London (1983)"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"32_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/978-3-642-02927-1_59","volume-title":"Automata, Languages and Programming","author":"J. Nederlof","year":"2009","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using m\u00f6bius inversion: Improving on steiner tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 713\u2013725. Springer, Heidelberg (2009)"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, USA (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"2","key":"32_CR19","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V. Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make w-hard problems hard: Fpt algorithms for w-hard problems in graphs with no short cycles. Algorithmica\u00a052(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"32_CR20","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. Inf. Process. Lett.\u00a024(2), 133\u2013137 (1987)","journal-title":"Inf. Process. Lett."}],"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-642-45043-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T20:18:39Z","timestamp":1746044319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45043-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450426","9783642450433"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45043-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}