Approzimation Algorithms for the b-Edge Dominating Set Problem and Its Related Problems
The edge dominating set problem is one of the fundamental covering problems in the field of combinatorial optimization. In this paper, we consider the 6-edge dominating set problem, a generalized version of the edge dominating set problem. In this version, we are given a simple undirected graph G=(V, E) and a demand vector b ∈ ZE+. A set F of edges in G is called a b-edge dominating set if each edge e ∈ E is adjacent to at least b(e) edges in F, where we allow F to contain multiple copies of edges in E. Given a cost vector w ∈ QE+, the problem asks to find a minimum cost of a b-edge dominating set. We first show that there is a 8/3-approximation algorithm for this problem. We then consider approximation algorithms for other related problems.
Takuro Fukunaga Hiroshi Nagamochi
Department of Applied Mathematics and Physics Graduate School of Informatics, Kyoto University
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
747-756
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）