{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:35:47Z","timestamp":1725478547708},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540695134"},{"type":"electronic","value":"9783540695141"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_9","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T05:47:40Z","timestamp":1169617660000},"page":"108-120","source":"Crossref","is-referenced-by-count":2,"title":["Improved Approximation Bounds for Edge Dominating Set in Dense Graphs"],"prefix":"10.1007","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Eythan","family":"Levy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/11533719_71","volume-title":"Computing and Combinatorics","author":"J. Cardinal","year":"2005","unstructured":"Cardinal, J., Labb\u00e9, M., Langerman, S., Levy, E., M\u00e9lot, H.: A tight analysis of the maximal matching heuristic. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 701\u2013709. Springer, Heidelberg (2005)"},{"key":"9_CR2","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 2 1\/10-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":"3","key":"9_CR3","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-006-7908-0","volume":"11","author":"M. Chleb\u00eck","year":"2006","unstructured":"Chleb\u00eck, M., Chleb\u00eckov\u00e0, J.: Approximation hardness of edge dominating set problems. Journal of Combinatorial Optimization\u00a011(3), 279\u2013290 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"key":"9_CR4","first-page":"58","volume-title":"Proc. of SOR","author":"A.V. Eremeev","year":"1999","unstructured":"Eremeev, A.V.: On some approximation algorithms for dense vertex cover problem. In: Proc. of SOR, pp. 58\u201362. Springer, Heidelberg (1999)"},{"key":"9_CR5","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":"9_CR6","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 and Company, New York (1979)"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. Siam Journal on Computing\u00a031, 1608\u20131623 (2002)","journal-title":"Siam Journal on Computing"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0406030","volume":"6","author":"J.D. Horton","year":"1993","unstructured":"Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math.\u00a06, 375\u2013387 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR9","unstructured":"Imamura, T., Iwama, K.: Approximating vertex cover on dense graphs. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 582\u2013589 (2005)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Zelikovsky, A.: Approximating dense cases of covering problems. In: Pardalos, P., Du, D. (eds.) Proc. of the DIMACS Workshop on Network Design: Connectivity and Facilites Location. DIMACS series in Disc. Math. and Theor. Comp. Sci., vol.\u00a040, pp. 169\u2013178 (1997)","DOI":"10.1090\/dimacs\/040\/11"},{"key":"9_CR11","unstructured":"M\u00e9lot, H.: Facets Defining Inequalities among Graph Invariants: the system GraPHedron (2005) (Submitted)"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0020-0190(95)94093-8","volume":"56","author":"A. Srinivasan","year":"1995","unstructured":"Srinivasan, A., Madhukar, K., Navagamsi, P., Pandu Rangan, C., Chang, M.-S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Inf. Proc. Letters\u00a056, 165\u2013171 (1995)","journal-title":"Inf. Proc. Letters"},{"issue":"3","key":"9_CR13","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","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:23:55Z","timestamp":1619508235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11970125_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}