{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:14:54Z","timestamp":1725524094410},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540939795"},{"type":"electronic","value":"9783540939801"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-93980-1_21","type":"book-chapter","created":{"date-parts":[[2009,1,12]],"date-time":"2009-01-12T00:12:21Z","timestamp":1231719141000},"page":"267-278","source":"Crossref","is-referenced-by-count":7,"title":["A $(2 - c \\frac{\\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem"],"prefix":"10.1007","author":[{"given":"Zvi","family":"Gotthilf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Rainshmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"key":"21_CR2","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"21_CR3","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-006-7908-0","volume":"11","author":"M. Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkova, J.: Approximation hardness of edge dominating set problems. Journal of Combinatorial Optimization\u00a011(3), 279\u2013290 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"21_CR4","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(3), 317\u2013326 (2001)","journal-title":"Journal of Combinatorial Optimization"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/11970125_9","volume-title":"Approximation and Online Algorithms","author":"J. Cardinal","year":"2007","unstructured":"Cardinal, J., Langerman, S., Levy, E.: Improved Approximation Bounds for Edge Dominating Set in Dense Graphs. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol.\u00a04368, pp. 108\u2013120. Springer, Heidelberg (2007)"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(00)00383-8","volume":"181","author":"T. Fujito","year":"2002","unstructured":"Fujito, T., Nagamochi, H.: A 2-Approximation Algorithm for the Minimum weight edge dominating set problem. Discrete Applied Mathematics\u00a0181, 199\u2013207 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR7","series-title":"A guide to the theory of NP-completeness","volume-title":"Computers and intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Co., New York (1979)"},{"issue":"5","key":"21_CR8","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(5), 1608\u20131623 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"21_CR9","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theorey","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theorey. Addison-Wesley, Reading (1969)"},{"issue":"3","key":"21_CR10","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 Journal on Discrete Mathematics\u00a06(3), 375\u2013387 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"21_CR11","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. Journal of Algorithms\u00a026(2), 238\u2013274 (1998)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"21_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., Nagavamsi, P., Rangan, C.P., Chang, M.S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Information Processing Letters\u00a056(3), 165\u2013171 (1995)","journal-title":"Information Processing Letters"},{"key":"21_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 Journal on Applied Mathematics\u00a038, 364\u2013372 (1980)","journal-title":"SIAM Journal on Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-93980-1_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T17:27:24Z","timestamp":1551720444000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-93980-1_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540939795","9783540939801"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-93980-1_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}