A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
From MaRDI portal
Publication:5952320
DOI10.1023/A:1011445210568zbMath1078.90061MaRDI QIDQ5952320
Toshihiro Fujito, Goran Konjevod, Ojas Parekh, Robert D. Carr
Publication date: 2001
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
90C35: Programming involving graphs or networks
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)