{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:40Z","timestamp":1742617240282,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642280757"},{"type":"electronic","value":"9783642280764"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28076-4_5","type":"book-chapter","created":{"date-parts":[[2012,2,27]],"date-time":"2012-02-27T13:53:14Z","timestamp":1330350794000},"page":"17-27","source":"Crossref","is-referenced-by-count":0,"title":["Generalized Above Guarantee Vertex Cover and r-Partization"],"prefix":"10.1007","author":[{"given":"R.","family":"Krithika","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters\u00a032, 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Kratsch, S.: On polynomial kernels for structural parameterizations of odd cycle transversal. To appear in Proceedings of IPEC 2011 (2011)","DOI":"10.1007\/978-3-642-28050-4_11"},{"key":"5_CR4","unstructured":"West, D.B.: Introduction to graph theory. Prentice Hall of India (2003)"},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0166-218X(88)90086-8","volume":"22","author":"D.G. Corneil","year":"1989","unstructured":"Corneil, D.G., Fonlupt, J.: The complexity of generalized clique covering. Discrete Applied Mathematics\u00a022(2), 109\u2013118 (1989)","journal-title":"Discrete Applied Mathematics"},{"issue":"7","key":"5_CR6","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"F.N. Abu-Khzama","year":"2010","unstructured":"Abu-Khzama, F.N.: A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences\u00a076(7), 524\u2013531 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00224-010-9262-y","volume":"48","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory of Computing Systems\u00a048, 402\u2013410 (2011)","journal-title":"Theory of Computing Systems"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-540-70575-8_45","volume-title":"Automata, Languages and Programming","author":"I. Razgon","year":"2008","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 551\u2013562. Springer, Heidelberg (2008)"},{"key":"5_CR9","volume-title":"Parameterized complexity theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Heidelberg (2006)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences\u00a067, 789\u2013807 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"7","key":"5_CR11","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.dam.2008.08.020","volume":"158","author":"L.A. Berry","year":"2010","unstructured":"Berry, L.A., 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":"5_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. To appear in Proceedings of IPEC 2011 (2011)","DOI":"10.1007\/978-3-642-28050-4_1"},{"key":"5_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, Heidelberg (1988)"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: Maxsat and maxcut. Journal of Algorithms\u00a031, 335\u2013354 (1999)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. Journal of Computer and System Sciences\u00a075(2), 137\u2013153 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR16","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures and upper bounds for satisfiability and related problems. PhD thesis, Department of Computer and Information Science, Link\u00f6pings universitet, Sweden (2007)"},{"issue":"2","key":"5_CR17","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. Information Processing Letters\u00a024(2), 133\u2013137 (1987)","journal-title":"Information Processing Letters"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Academic Press (1980)","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"5_CR19","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H.Freeman and Company (1979)"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of k-sat. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pp. 237\u2013240 (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"5_CR21","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"5_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, Heidelberg (1999)"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-540-77120-3_25","volume-title":"Algorithms and Computation","author":"S. Mishra","year":"2007","unstructured":"Mishra, S., Raman, V., Saurabh, S., Sikdar, S., Subramanian, C.R.: The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 268\u2013279. Springer, Heidelberg (2007)"},{"issue":"4","key":"5_CR25","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1007\/s00453-010-9412-2","volume":"61","author":"S. Mishra","year":"2011","unstructured":"Mishra, S., Raman, V., Saurabh, S., Sikdar, S., Subramanian, C.R.: The complexity of k\u00f6nig subgraph problems and above-guarantee vertex cover. Algorithmica\u00a061(4), 857\u2013881 (2011)","journal-title":"Algorithmica"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-23719-5_33","volume-title":"Algorithms \u2013 ESA 2011","author":"V. Raman","year":"2011","unstructured":"Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, Flowers and Vertex Cover. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 382\u2013393. Springer, Heidelberg (2011)"},{"issue":"30","key":"5_CR27","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00224-007-1334-2","volume":"41","author":"V. Raman","year":"2007","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theory of Computing Systems\u00a041(30), 563\u2013587 (2007)","journal-title":"Theory of Computing Systems"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28076-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T01:26:27Z","timestamp":1742606787000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28076-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642280757","9783642280764"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28076-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}