{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T12:37:31Z","timestamp":1754483851469},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","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-33293-7_5","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T06:50:58Z","timestamp":1346223058000},"page":"25-36","source":"Crossref","is-referenced-by-count":5,"title":["New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set"],"prefix":"10.1007","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","reference":[{"key":"5_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-17493-3_6","volume-title":"Parameterized and Exact Computation","author":"D. Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D., Fernau, H.: Enumerate and Measure: Improving Parameter Budget Management. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 38\u201349. Springer, Heidelberg (2010)"},{"issue":"17","key":"5_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.T.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Applied Mathematics\u00a0159(17), 1954\u20131970 (2011)","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-642-17517-6_35","volume-title":"Algorithms and Computation","author":"L. Brankovic","year":"2010","unstructured":"Brankovic, L., Fernau, H.: Combining Two Worlds: Parameterised Approximation for Vertex Cover. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol.\u00a06506, pp. 390\u2013402. Springer, Heidelberg (2010)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11847250_9","volume-title":"Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Huang, X.: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 96\u2013108. Springer, Heidelberg (2006)"},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1023\/A:1011445210568","volume":"5","author":"R.D. Carr","year":"2001","unstructured":"Carr, R.D., Fujito, T., Konjevod, G., Parekh, O.: A \n                  \n                    \n                  \n                  $2\\frac{1}{10}$\n                -Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem. J. Comb. Optim.\u00a05(3), 317\u2013326 (2001)","journal-title":"J. Comb. Optim."},{"issue":"8-10","key":"5_CR6","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0410(8-10), 949\u2013957 (2009)","journal-title":"Theoretical Computer Science"},{"key":"5_CR7","doi-asserted-by":"publisher","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 \n                  \n                    \n                  \n                  $2\\frac{1}{10}$\n                -approximation algorithm for a generalization of the weighted edge-dominating set problem. Journal of Combinatorial Optimization\u00a05, 317\u2013326 (2001)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"40-42","key":"5_CR8","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0411(40-42), 3736\u20133756 (2010)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"5_CR9","doi-asserted-by":"publisher","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. Journal of Combinatorial Optimization\u00a011(3), 279\u2013290 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, M.: The importance of being biased. In: Proc. STOC 2002, pp. 33\u201342 (2002)","DOI":"10.1145\/509907.509915"},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"R.G. Downey","year":"2008","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C., Rosamond, F.A.: Parameterized approximation of dominating set problems. Inf. Process. Lett.\u00a0109(1), 68\u201370 (2008)","journal-title":"Inf. Process. Lett."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximability and fixed parameter approximability of edge dominating set (manuscript, 2012)","DOI":"10.1007\/978-3-642-33293-7_5"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-31594-7_30","volume-title":"Automata, Languages, and Programming","author":"M.R. Fellows","year":"2012","unstructured":"Fellows, M.R., Kulik, A., Rosamond, F., Shachnai, H.: Parameterized Approximation via Fidelity Preserving Transformations. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 351\u2013362. Springer, Heidelberg (2012)"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/11847250_13","volume-title":"Parameterized and Exact Computation","author":"H. Fernau","year":"2006","unstructured":"Fernau, H.: Edge Dominating Set: Efficient Enumeration-Based Exact Algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 142\u2013153. Springer, Heidelberg (2006)"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"F. Fomin","year":"2009","unstructured":"Fomin, F., Gaspers, S., Saurabh, S., Stepanov, A.: On two techniques of combining branching and treewidth. Algorithmica\u00a054(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"5_CR16","doi-asserted-by":"publisher","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. Discrete Appl. Math.\u00a0118, 199\u2013207 (2002)","journal-title":"Discrete Appl. Math."},{"key":"5_CR17","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"issue":"3","key":"5_CR18","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-epsilon. J. Comput. Syst. Sci.\u00a074(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"5_CR19","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal\u00a051(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"issue":"3","key":"5_CR20","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00224-007-1334-2","volume":"42","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\u00a042(3), 563\u2013587 (2007)","journal-title":"Theory of Computing Systems"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-540-79723-4_20","volume-title":"Parameterized and Exact Computation","author":"J.M.M. Rooij van","year":"2008","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact Algorithms for Edge Domination. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 214\u2013225. Springer, Heidelberg (2008)"},{"issue":"1","key":"5_CR22","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0414(1), 92\u201399 (2012)","journal-title":"Theoretical Computer Science"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1007\/978-3-642-22993-0_54","volume-title":"Mathematical Foundations of Computer Science 2011","author":"M. Xiao","year":"2011","unstructured":"Xiao, M., Kloks, T., Poon, S.-H.: New Parameterized Algorithms for the Edge Dominating Set Problem. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 604\u2013615. Springer, Heidelberg (2011)"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-642-21204-8_14","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"M. Xiao","year":"2011","unstructured":"Xiao, M., Nagamochi, H.: Parameterized Edge Dominating Set in Cubic Graphs (Extended Abstract). In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol.\u00a06681, pp. 100\u2013112. Springer, Heidelberg (2011)"},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-642-29952-0_36","volume-title":"Theory and Applications of Models of Computation","author":"M. Xiao","year":"2012","unstructured":"Xiao, M., Nagamochi, H.: A Refined Exact Algorithm for Edge Dominating Set. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol.\u00a07287, pp. 360\u2013372. Springer, Heidelberg (2012)"},{"issue":"3","key":"5_CR26","doi-asserted-by":"publisher","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. Appl. Math.\u00a038(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:06:16Z","timestamp":1558299976000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}