{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:55:20Z","timestamp":1774418120449,"version":"3.50.1"},"reference-count":19,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2002,5,1]],"date-time":"2002-05-01T00:00:00Z","timestamp":1020211200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4095,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2002,5]]},"DOI":"10.1016\/s0166-218x(00)00383-8","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T07:07:35Z","timestamp":1027580855000},"page":"199-207","source":"Crossref","is-referenced-by-count":53,"title":["A 2-approximation algorithm for the minimum weight edge dominating set problem"],"prefix":"10.1016","volume":"118","author":[{"given":"Toshihiro","family":"Fujito","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00383-8_BIB1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, Proceedings of the 33rd FOCS, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","article-title":"Approximation algorithms for NP-complete problems on planar graphs","volume":"41","author":"Baker","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB3","doi-asserted-by":"crossref","unstructured":"R. Carr, T. Fujito, G. Konjevod, O. Parekh, A 2110-approximation algorithm for a generalization of the weighted edge-dominating set problem, in: Proceedings of the Eighth ESA, 2000, pp. 132\u2013142.","DOI":"10.1007\/3-540-45253-2_13"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","article-title":"Maximum matching and a polyhedron with 0,1-vertices","volume":"69","author":"Edmonds","year":"1965","journal-title":"J. Res. Nat. Bur. Standards B"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB5","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Canad. J. Math."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB6","unstructured":"J. Edmonds, E.L. Johnson, Matching, a well solved class of integer linear programs, in: Combinatorial Structures and Their Applications, eds., R. Guy, H. Hanani, N. Sauer and J. Sch\u00f6nheim, Gordon and Breach, New York, 1970, pp. 89\u201392."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB7","doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of lnn for approximating set cover, Proceedings of the 28th STOC, 1996, pp. 314\u2013318.","DOI":"10.1145\/237814.237977"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB8","first-page":"373","article-title":"Kritische Graphen II","volume":"8","author":"Gallai","year":"1963","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB9","first-page":"401","article-title":"Maximale Systeme unabh\u00e4ngiger Kanten","volume":"9","author":"Gallai","year":"1964","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB10","series-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel","year":"1988"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB11","series-title":"Graph Theory","author":"Harary","year":"1969"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB12","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal in-approximability results, Proceedings of the 29th STOC, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB13","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0406030","article-title":"Minimum edge dominating sets","volume":"6","author":"Horton","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB14","doi-asserted-by":"crossref","unstructured":"H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Proceedings of the Second ESA, 1994, pp. 424\u2013435.","DOI":"10.1007\/BFb0049428"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB15","series-title":"Matching Theory","author":"Lov\u00e1sz","year":"1986"},{"key":"10.1016\/S0166-218X(00)00383-8_BIB16","unstructured":"S. Mitchell, S. Hedetniemi, Edge domination in trees, Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1977, pp. 489\u2013509."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB18","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0190(95)94093-8","article-title":"Edge domination on bipartite permutation graphs and cotriangulated graphs","volume":"56","author":"Srinivasan","year":"1995","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(00)00383-8_BIB19","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","article-title":"Edge dominating sets in graphs","volume":"38","author":"Yannakakis","year":"1980","journal-title":"SIAM J. Appl. Math."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00003838?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00003838?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T00:10:37Z","timestamp":1578442237000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00003838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,5]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2002,5]]}},"alternative-id":["S0166218X00003838"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00383-8","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2002,5]]}}}