{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:55:18Z","timestamp":1774418118990,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,10,6]],"date-time":"2007-10-06T00:00:00Z","timestamp":1191628800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s00453-007-9057-y","type":"journal-article","created":{"date-parts":[[2007,10,5]],"date-time":"2007-10-05T11:23:15Z","timestamp":1191583395000},"page":"244-254","source":"Crossref","is-referenced-by-count":17,"title":["Linear Time Algorithms for Generalized Edge Dominating Set Problems"],"prefix":"10.1007","volume":"50","author":[{"given":"Andr\u00e9","family":"Berger","sequence":"first","affiliation":[]},{"given":"Ojas","family":"Parekh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,6]]},"reference":[{"key":"9057_CR1","unstructured":"Berger, A., Fukunaga, T., Nagamochi, H., Parekh, O.: Capacitated b-edge dominating set and related problems. Manuscript (2005)"},{"key":"9057_CR2","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-approximation algorithm for a generalization of the weighted edge-dominating set problem. J. Comb. Optim. 5, 317\u2013326 (2001)","journal-title":"J. Comb. Optim."},{"key":"9057_CR3","unstructured":"Fricke, G., Laskar, R.: Strong matchings on trees. In: Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1992, vol. 89, pp. 239\u2013243 (1992)"},{"issue":"6","key":"9057_CR4","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0020-0190(01)00138-7","volume":"79","author":"T. Fujito","year":"2001","unstructured":"Fujito, T.: On approximability of the independent\/connected edge dominating set problems. Inf. Process. Lett. 79(6), 261\u2013266 (2001)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9057_CR5","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. Discrete Appl. Math. 118(3), 199\u2013207 (2002)","journal-title":"Discrete Appl. Math."},{"key":"9057_CR6","first-page":"1192","volume":"254","author":"A. Ghouila-Houri","year":"1962","unstructured":"Ghouila-Houri, A.: Caract\u00e9risation des matrices totalement unimodulaires. C. R. Acad. Sci. Paris 254, 1192\u20131194 (1962)","journal-title":"C. R. Acad. Sci. Paris"},{"key":"9057_CR7","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)"},{"key":"9057_CR8","series-title":"Annals of Mathematics Studies","first-page":"223","volume-title":"Linear Inequalities and Related Systems","author":"A.J. Hoffman","year":"1956","unstructured":"Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems. Annals of Mathematics Studies, vol. 38, pp. 223\u2013246. Princeton University Press, Princeton (1956)"},{"issue":"3","key":"9057_CR9","doi-asserted-by":"crossref","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. 6(3), 375\u2013387 (1993)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9057_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.7151\/dmgt.1006","volume":"15","author":"S.F. Hwang","year":"1995","unstructured":"Hwang, S.F., Chang, G.J.: The edge domination problem. Discuss. Math. Graph Theory 15(1), 51\u201357 (1995)","journal-title":"Discuss. Math. Graph Theory"},{"key":"9057_CR11","unstructured":"Mitchell, S.L., Hedetniemi, S.T.: Edge domination in trees. In: Proc. of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, LA, 1977, pp. 489\u2013509 (1977)"},{"issue":"3","key":"9057_CR12","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9057_CR13","first-page":"287","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02)","author":"O. Parekh","year":"2002","unstructured":"Parekh, O.: Edge dominating and hypomatchable sets. In: Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02), pp. 287\u2013291. ACM Press, New York (2002)"},{"key":"9057_CR14","unstructured":"Parekh, O.: Polyhedral techniques for graphic covering problems. Ph.D. thesis, Carnegie Mellon University (2002)"},{"key":"9057_CR15","unstructured":"Parekh, O., Razouk, N.: A generalization of Gallai\u2019s theorem. Manuscript (2005)"},{"key":"9057_CR16","series-title":"Lect. Notes in Comp. Sci.","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-49116-3_24","volume-title":"STACS 99 (Trier)","author":"R. Preis","year":"1999","unstructured":"Preis, R.: Linear time $\\frac{1}{2}$ -approximation algorithm for maximum weighted matching in general graphs. In: STACS 99 (Trier). Lect. Notes in Comp. Sci., vol. 1563, pp. 259\u2013269. Springer, Berlin (1999)"},{"key":"9057_CR17","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, Berlin (2003)"},{"issue":"3","key":"9057_CR18","doi-asserted-by":"crossref","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., Pandu Rangan, C., Chang, M.-S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Inf. Process. Lett. 56(3), 165\u2013171 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9057_CR19","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, New York (2001)"},{"issue":"3","key":"9057_CR20","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. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9057-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9057-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9057-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:00Z","timestamp":1559123100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9057-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["9057"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9057-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,6]]}}}