{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:02:05Z","timestamp":1725562925739},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_48","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"549-555","source":"Crossref","is-referenced-by-count":2,"title":["Solving minones-2-sat as Fast as vertex cover"],"prefix":"10.1007","author":[{"given":"Neeldhara","family":"Misra","sequence":"first","affiliation":[]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]},{"given":"Bal Sri","family":"Shankar","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"48_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/978-3-540-73951-7_38","volume-title":"Algorithms and Data Structures","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N.: Kernelization algorithms for d-hitting set problems. In: Dehne, F.K.H.A., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 434\u2013445. Springer, Heidelberg (2007)"},{"unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, algorithms and applications. Springer Publishing Company, Heidelberg (2008) (incorporated)","key":"48_CR2"},{"key":"48_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11821069_21","volume-title":"Mathematical Foundations of Computer Science 2006","author":"J. Chen","year":"2006","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 238\u2013249. Springer, Heidelberg (2006)"},{"key":"48_CR4","volume-title":"Introduction to algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT Press, Cambridge (2001)"},{"key":"48_CR5","doi-asserted-by":"crossref","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 (November 1999)"},{"unstructured":"Dahll\u00f6f, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: SODA, pp. 292\u2013298 (2002)","key":"48_CR6"},{"key":"48_CR7","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01758838","volume":"8","author":"D. Gusfield","year":"1992","unstructured":"Gusfield, D., Pitt, L.: A bounded approximation for the minimum cost 2-sat problem. Algorithmica\u00a08, 103\u2013117 (1992)","journal-title":"Algorithmica"},{"key":"48_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"D. Hochbaum","year":"1993","unstructured":"Hochbaum, D., Meggido, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Mathematical Programming\u00a062, 69\u201383 (1993)","journal-title":"Mathematical Programming"},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","unstructured":"Hochbaum, D.S. (ed.): Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston (1997)","key":"48_CR9"},{"unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Kannan, R., Kumar, N. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol.\u00a04, pp. 287\u2013298. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2009)","key":"48_CR10"},{"key":"48_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-642-11269-0_22","volume-title":"IWPEC 2009","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 264\u2013275. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Preprocessing of min ones problems: A dichotomy. In: 37th International Colloquium on Automata, Languages and Programming, ICALP (to appear 2010)","key":"48_CR12","DOI":"10.1007\/978-3-642-14165-2_55"},{"issue":"2","key":"48_CR13","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. J. Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"48_CR14","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed parameter algorithms (oxford lecture series in mathematics and its applications)","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed parameter algorithms (oxford lecture series in mathematics and its applications). Oxford University Press, USA (March 2006)"},{"issue":"2","key":"48_CR15","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms\u00a047(2), 63\u201377 (2003)","journal-title":"J. Algorithms"},{"key":"48_CR16","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:46Z","timestamp":1606186906000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}