{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:11Z","timestamp":1759638251767},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,6,13]],"date-time":"2014-06-13T00:00:00Z","timestamp":1402617600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s00224-014-9549-5","type":"journal-article","created":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T03:04:16Z","timestamp":1402542256000},"page":"330-346","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set"],"prefix":"10.1007","volume":"56","author":[{"given":"Bruno","family":"Escoffier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,6,13]]},"reference":[{"key":"9549_CR1","doi-asserted-by":"crossref","unstructured":"Binkele-Raible, D., Fernau, H.: Enumerate and measure: improving parameter budget management. In: Raman, V., Saurabh, S. (eds.) Proc. International Symposium on Parameterized and Exact Computation, IPEC\u201910, volume 6478 of Lecture Notes in Computer Science, pp 38\u201349. Springer-Verlag (2010)","DOI":"10.1007\/978-3-642-17493-3_6"},{"issue":"17","key":"9549_CR2","doi-asserted-by":"crossref","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V. Th.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954\u20131970 (2011)","journal-title":"Discret. Appl. Math."},{"key":"9549_CR3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2012.12.003","volume":"511","author":"L Brankovic","year":"2013","unstructured":"Brankovic, L., Fernau, H.: A novel parameterised approximation algorithm for minimum vertex cover. Theor. Comput. Sci. 511, 85\u2013108 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9549_CR4","doi-asserted-by":"crossref","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC\u201906, volume 4169 of Lecture Notes in Computer Science, pp 96\u2013108. Springer-Verlag (2006)","DOI":"10.1007\/11847250_9"},{"issue":"8-10","key":"9549_CR5","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1016\/j.tcs.2008.12.036","volume":"410","author":"J Cardinal","year":"2009","unstructured":"Cardinal, J., Langerman, S., Levy, E.: Improved approximation bounds for edge dominating set in dense graphs. Theoret. Comput. Sci. 410(8-10), 949\u2013957 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"9549_CR6","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1023\/A:1011445210568","volume":"5","author":"R Carr","year":"2001","unstructured":"Carr, R., Fujito, T., Konjevod, G., Parekh, O.: A ( 2 + 1 10 ) $(2+\\frac {1}{10})$ -approximation algorithm for a generalization of the weighted edge-dominating set problem. J. Comb. Optim. 5, 317\u2013326 (2001)","journal-title":"J. Comb. Optim."},{"issue":"40-42","key":"9549_CR7","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40-42), 3736\u20133756 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9549_CR8","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10878-006-7908-0","volume":"11","author":"M Chlebik","year":"2006","unstructured":"Chlebik, M., Chlebikova, J.: Approximation hardness of edge dominating set problems. J. Comb. Optim. 11(3), 279\u2013290 (2006)","journal-title":"J. Comb. Optim."},{"key":"9549_CR9","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, M.: The importance of being biased. Proc. STOC\u201902, 33\u201342 (2002)","DOI":"10.1145\/509914.509915"},{"issue":"1","key":"9549_CR10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"RG Downey","year":"2008","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C., Rosamond, F.A.: Parameterized approximation of dominating set problems. Inform. Process. Lett. 109(1), 68\u201370 (2008)","journal-title":"Inform. Process. Lett."},{"key":"9549_CR11","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Kulik, A., Rosamond, F.A., Shachnai, H.: Parameterized approximation via fidelity preserving transformations. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) Proc. ICALP\u201912, volume 7391 of Lecture Notes in Computer Science, pp 351\u2013362. Springer-Verlag (2012)","DOI":"10.1007\/978-3-642-31594-7_30"},{"key":"9549_CR12","doi-asserted-by":"crossref","unstructured":"Fernau, H.: Edge dominating set: efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC\u201906, volume 4169 of Lecture Notes in Computer Science, pp 142\u2013153. Springer-Verlag (2006)","DOI":"10.1007\/11847250_13"},{"issue":"2","key":"9549_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"9549_CR14","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"118","author":"T Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discret. Appl. Math. 118, 199\u2013207 (2002)","journal-title":"Discret. Appl. Math."},{"key":"9549_CR15","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)"},{"issue":"3","key":"9549_CR16","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 \u2212 \u03b5. J. Comput. System Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"9549_CR17","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"9549_CR18","doi-asserted-by":"crossref","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 Comput. Syst. 41(3), 563\u2013587 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9549_CR19","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.tcs.2011.10.001","volume":"414","author":"R Schmied","year":"2012","unstructured":"Schmied, R., Viehmann, C.: Approximating edge dominating set in dense graphs. Theoret. Comput. Sci. 414(1), 92\u201399 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"9549_CR20","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1007\/s00453-011-9546-x","volume":"64","author":"JMM Rooij van","year":"2012","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact Algorithms for Edge Domination. Algorithmica 64(4), 535\u2013563 (2012)","journal-title":"Algorithmica"},{"key":"9549_CR21","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.tcs.2012.06.022","volume":"511","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Kloks, T., Poon, S.-H.: New parameterized algorithms for the edge dominating set problem. Theor. Comput. Sci. 511, 147\u2013158 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9549_CR22","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2012.08.015","volume":"508","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Nagamochi, H.: Parameterized edge dominating set in graphs with degree bounded by 3. Theor. Comput. Sci. 508, 2\u201315 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9549_CR23","doi-asserted-by":"crossref","unstructured":"Xiao, M., Nagamochi, H.: A refined exact algorithm for edge dominating set. In: Agrawal, M., Barry Cooper, S., Li, A. (eds.) Proc. Theory and Applications of Models of Computation, TAMC\u201912, volume 7287 of Lecture Notes in Computer Science, pp 360\u2013372. Springer-Verlag (2012)","DOI":"10.1007\/978-3-642-29952-0_36"},{"issue":"3","key":"9549_CR24","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. App. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. App. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9549-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9549-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9549-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T09:08:03Z","timestamp":1565514483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9549-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,13]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9549"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9549-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,13]]}}}