TY - GEN
T1 - The prize-collecting edge dominating set problem in trees
AU - Kamiyama, Naoyuki
PY - 2010/11/22
Y1 - 2010/11/22
N2 - In this paper, we consider the prize-collecting edge dominating set problem, which is a generalization of the edge dominating set problem. In the prize-collecting edge dominating set problem, we are not forced to dominate all edges, but we need to pay penalties for edges which are not dominated. It is known that this problem is script N P-hard, and Parekh presented a 8/3-approximation algorithm. To the best of our knowledge, no polynomial-time solvable case is known for this problem. In this paper, we show that the prize-collecting edge dominating set problem in trees can be solved in polynomial time.
AB - In this paper, we consider the prize-collecting edge dominating set problem, which is a generalization of the edge dominating set problem. In the prize-collecting edge dominating set problem, we are not forced to dominate all edges, but we need to pay penalties for edges which are not dominated. It is known that this problem is script N P-hard, and Parekh presented a 8/3-approximation algorithm. To the best of our knowledge, no polynomial-time solvable case is known for this problem. In this paper, we show that the prize-collecting edge dominating set problem in trees can be solved in polynomial time.
UR - http://www.scopus.com/inward/record.url?scp=78349297517&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78349297517&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15155-2_41
DO - 10.1007/978-3-642-15155-2_41
M3 - Conference contribution
AN - SCOPUS:78349297517
SN - 364215154X
SN - 9783642151545
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 465
EP - 476
BT - Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings
T2 - 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010
Y2 - 23 August 2010 through 27 August 2010
ER -