{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:36Z","timestamp":1759638996035},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T00:00:00Z","timestamp":1494201600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00453-017-0315-3","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T14:02:43Z","timestamp":1494252163000},"page":"2221-2239","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximability of Clique Transversal in Perfect Graphs"],"prefix":"10.1007","volume":"80","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","published-online":{"date-parts":[[2017,5,8]]},"reference":[{"issue":"7","key":"315_CR1","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for $$d$$ d -hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"315_CR2","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Fernau, H.: Kernels: annotated, proper and induced. In: Parameterized and Exact Computation, Volume 4169 of Lecture Notes in Computer Science, pp. 264\u2013275. Springer, Berlin (2006)","DOI":"10.1007\/11847250_24"},{"key":"315_CR3","first-page":"114","volume":"10","author":"C Berge","year":"1961","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)","journal-title":"Wissenschaftliche Zeitschrift, Martin Luther Universit\u00e4t Halle-Wittenberg Mathematisch-Naturwissenschaftliche Reihe"},{"issue":"7","key":"315_CR4","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1016\/j.dam.2008.08.020","volume":"158","author":"LA Berry","year":"2010","unstructured":"Berry, L.A., Kennedy, W.S., King, A.D., Li, Z., Reed, B.A.: Finding a maximum-weight induced $$k$$ k -partite subgraph of an $$i$$ i -triangulated graph. Discret. Appl. Math. 158(7), 765\u2013770 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"315_CR5","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P.D., Vuskovi\u0107, K.: Recognizing berge graphs. Combinatorica 25(2), 143\u2013186 (2005)","journal-title":"Combinatorica"},{"key":"315_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F\u00a0.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"315_CR7","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 67, 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"315_CR8","doi-asserted-by":"crossref","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. Ann. Math. 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"issue":"1","key":"315_CR9","doi-asserted-by":"crossref","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. Ann. Math. 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math."},{"issue":"4","key":"315_CR10","doi-asserted-by":"crossref","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014)","journal-title":"J. ACM"},{"key":"315_CR11","first-page":"6","volume":"21","author":"V Guruswami","year":"2014","unstructured":"Guruswami, V., Lee, E.: Inapproximability of feedback vertex set for bounded length cycles. Electron. Colloq. Comput. Complex. 21, 6 (2014)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"315_CR12","doi-asserted-by":"crossref","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, Berlin (1988)"},{"key":"315_CR13","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"315_CR14","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D\u00a0S Hochbaum","year":"1997","unstructured":"Hochbaum, D\u00a0.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Co, Boston (1997)"},{"key":"315_CR15","doi-asserted-by":"crossref","unstructured":"Iwata, Y., Oka, K., Yuichi, Y.: Linear-time FPT algorithms via network flow. In: Proceedings of the ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 1749\u20131761 (2014)","DOI":"10.1137\/1.9781611973402.127"},{"key":"315_CR16","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of k-SAT. In: Proceedings of IEEE Conference on Computational Complexity, pp. 237\u2013240 (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"315_CR17","doi-asserted-by":"crossref","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377\u20131411 (2016)","journal-title":"SIAM J. Comput."},{"issue":"22\u201324","key":"315_CR18","doi-asserted-by":"crossref","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. Inf. Process. Lett. 113(22\u201324), 849\u2013851 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"315_CR19","doi-asserted-by":"crossref","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)$$ ( r , l ) -partization. J. Graph Algorithms Appl. 17(2), 129\u2013146 (2013)","journal-title":"J. Graph Algorithms Appl."},{"issue":"A1","key":"315_CR20","first-page":"1","volume":"1","author":"DE Knuth","year":"1994","unstructured":"Knuth, D.E.: The sandwich theorem. Electron. J. Comb. 1(A1), 1\u201348 (1994)","journal-title":"Electron. J. Comb."},{"issue":"3","key":"315_CR21","doi-asserted-by":"crossref","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-\\epsilon $$ 2 - \u03f5 . J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"315_CR22","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N\u00a0.S., Raman, V., Ramanujan, M\u00a0.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"315_CR23","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discret. Math. 2(3), 253\u2013267 (1972)","journal-title":"Discret. Math."},{"key":"315_CR24","unstructured":"Lov\u00e1sz, L.: On Minimax Theorems of Combinatorics. Ph.D thesis, Matemathikai Lapok, vol. 26, pp. 209\u2013264 (1975)"},{"issue":"2","key":"315_CR25","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"315_CR26","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"GL Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48\u201361 (1974)","journal-title":"Math. Program."},{"issue":"1","key":"315_CR27","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"315_CR28","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"BA Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32, 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"315_CR29","doi-asserted-by":"crossref","unstructured":"Wagler, A.: Critical and anticritical edges in perfect graphs. In: Graph-Theoretic Concepts in Computer Science, Volume 2204 of Lecture Notes in Computer Science, pp. 317\u2013327 (2001)","DOI":"10.1007\/3-540-45477-2_29"},{"key":"315_CR30","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D\u00a0P Williamson","year":"2011","unstructured":"Williamson, D\u00a0.P., Shmoys, D\u00a0.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0315-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0315-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0315-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T20:26:51Z","timestamp":1569270411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0315-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,8]]},"references-count":30,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["315"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0315-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,8]]}}}