TY - GEN

T1 - New parameterized algorithms for the edge dominating set problem

AU - Xiao, Mingyu

AU - Kloks, Ton

AU - Poon, Sheung Hung

N1 - Funding Information:
The first author was supported in part by Grant 60903007 of NSFC, China. The second author was supported in part by Grant 99-2218-E-007-016 of NSC, Taiwan. The third author was supported in part by Grant 97-2221-E-007-054-MY3 of NSC, Taiwan.

PY - 2011

Y1 - 2011

N2 - An edge dominating set of a graph G = (V,E) is a subset M ⊆ E of edges in the graph such that each edge in E - M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem we are given a graph G = (V,E) and an integer k and we are asked to decide whether G has an edge dominating set of size at most k. In this paper we show that the parameterized edge dominating set problem can be solved in O*(2.3147 k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k 3) edges.

AB - An edge dominating set of a graph G = (V,E) is a subset M ⊆ E of edges in the graph such that each edge in E - M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem we are given a graph G = (V,E) and an integer k and we are asked to decide whether G has an edge dominating set of size at most k. In this paper we show that the parameterized edge dominating set problem can be solved in O*(2.3147 k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k 3) edges.

UR - http://www.scopus.com/inward/record.url?scp=80052105321&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22993-0_54

DO - 10.1007/978-3-642-22993-0_54

M3 - Conference contribution

AN - SCOPUS:80052105321

SN - 9783642229923

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 604

EP - 615

BT - Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings

T2 - 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011

Y2 - 22 August 2011 through 26 August 2011

ER -