{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:33:37Z","timestamp":1725798817920},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662447765"},{"type":"electronic","value":"9783662447772"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_36","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T10:43:15Z","timestamp":1408185795000},"page":"430-442","source":"Crossref","is-referenced-by-count":0,"title":["LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs"],"prefix":"10.1007","author":[{"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Krithika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"7","key":"36_CR1","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":"36_CR2","unstructured":"Berge, C.: F\u00e4rbung von graphen, deren s\u00e4mtliche bzw. deren ungerade kreise starr sind (zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universit\u00e4t Halle-Wittenberg Mathematisch-Naturwissenschaftliche Reihe 10, 114\u2013115 (1961)"},{"issue":"7","key":"36_CR3","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":"36_CR4","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":"1","key":"36_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R.: The strong perfect graph theorem. Annals of Mathematics\u00a0164(1), 51\u2013229 (2006)","journal-title":"Annals of Mathematics"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"Dell, H., Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 251\u2013260 (2010)","DOI":"10.1145\/1806689.1806725"},{"issue":"1","key":"36_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics\u00a0162(1), 439\u2013485 (2005)","journal-title":"Annals of Mathematics"},{"key":"36_CR8","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier Science B.V. (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"key":"36_CR10","first-page":"6","volume":"21","author":"V. Guruswami","year":"2014","unstructured":"Guruswami, V., Lee, E.: Inapproximability of feedback vertex set for bounded length cycles. Electronic Colloquium on Computational Complexity (ECCC)\u00a021, 6 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Oka, K., Yuichi, Y.: Linear-time fpt algorithms via network flow. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1749\u20131761 (2014)","DOI":"10.1137\/1.9781611973402.127"},{"issue":"3","key":"36_CR12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. Journal of Computer and System Sciences\u00a074(3), 335\u2013349 (2008)","journal-title":"Journal of Computer and System Sciences"},{"issue":"A1","key":"36_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"D. Knuth","year":"1994","unstructured":"Knuth, D.: The sandwich theorem. Electronic Journal of Combinatorics\u00a01(A1), 1\u201348 (1994)","journal-title":"Electronic Journal of Combinatorics"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: A randomized polynomial kernel for odd cycle transversal. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 94\u2013103 (2012)","DOI":"10.1137\/1.9781611973099.8"},{"issue":"22\u201324","key":"36_CR15","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ipl.2013.08.007","volume":"113","author":"R. Krithika","year":"2013","unstructured":"Krithika, R., Narayanaswamy, N.S.: Another disjoint compression algorithm for odd cycle transversal. Information Processing Letters\u00a0113(22\u201324), 849\u2013851 (2013)","journal-title":"Information Processing Letters"},{"issue":"2","key":"36_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.7155\/jgaa.00288","volume":"17","author":"R. Krithika","year":"2013","unstructured":"Krithika, R., Narayanaswamy, N.S.: Parameterized algorithms for (r,l)-partization. Journal of Graph Algorithms and Applications\u00a017(2), 129\u2013146 (2013)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"36_CR17","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. CoRR abs\/1203.0833. A preliminary version appeared in the Proceedings of STACS (2012)"},{"key":"36_CR18","unstructured":"Lov\u00e1sz, L.: On minimax theorems of combinatorics. Ph.D thesis, Matemathikai Lapok 26, 209\u2013264 (1975)"},{"issue":"1","key":"36_CR19","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"G.L. Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Mathematical Programming\u00a06(1), 48\u201361 (1974)","journal-title":"Mathematical Programming"},{"issue":"1","key":"36_CR20","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(1), 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"36_CR21","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":"36_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/3-540-45477-2_29","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Wagler","year":"2001","unstructured":"Wagler, A.: Critical and anticritical edges in perfect graphs. In: Brandst\u00e4dt, A., Van Le, B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 317\u2013327. Springer, Heidelberg (2001)"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: Half-integrality, lp-branching and fpt algorithms. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1762\u20131781 (2014)","DOI":"10.1137\/1.9781611973402.128"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,23]],"date-time":"2020-08-23T11:49:23Z","timestamp":1598183363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}