New parameterized algorithms for the edge dominating set problem

Mingyu Xiao; Ton Kloks; Sheung Hung Poon

doi:10.1016/j.tcs.2012.06.022

New parameterized algorithms for the edge dominating set problem

Mingyu Xiao, Ton Kloks, Sheung Hung Poon

Research output: Journal Publication › Article › peer-review

28 Citations (Scopus)

Abstract

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³) edges.

Original language	English
Pages (from-to)	147-158
Number of pages	12
Journal	Theoretical Computer Science
Volume	511
DOIs	https://doi.org/10.1016/j.tcs.2012.06.022
Publication status	Published - 4 Nov 2013
Externally published	Yes

Keywords

Edge dominating set
Graph algorithms
Kernelization
Parameterized algorithms

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2012.06.022

Cite this

@article{d7dfeada29974d78a50d00dabde90228,

title = "New parameterized algorithms for the edge dominating set problem",

abstract = "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.3147k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k3) edges.",

keywords = "Edge dominating set, Graph algorithms, Kernelization, Parameterized algorithms",

author = "Mingyu Xiao and Ton Kloks and Poon, {Sheung Hung}",

note = "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.",

year = "2013",

month = nov,

day = "4",

doi = "10.1016/j.tcs.2012.06.022",

language = "English",

volume = "511",

pages = "147--158",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

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 - 2013/11/4

Y1 - 2013/11/4

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.3147k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k3) 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.3147k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k3) edges.

KW - Edge dominating set

KW - Graph algorithms

KW - Kernelization

KW - Parameterized algorithms

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

U2 - 10.1016/j.tcs.2012.06.022

DO - 10.1016/j.tcs.2012.06.022

M3 - Article

AN - SCOPUS:84887992525

SN - 0304-3975

VL - 511

SP - 147

EP - 158

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

New parameterized algorithms for the edge dominating set problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this