
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Exact Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3
Mingyu XIAO Hiroshi NAGAMOCHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.3
pp.408418 Publication Date: 2013/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.408
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —) Category: Keyword: edge dominating sets, exact algorithms, cubic graphs,
Full Text: PDF(337.9KB)>>
Summary:
Given a graph G = (V,E) together with a nonnegative integer requirement on vertices r:V Z_{+}, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E  M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NPhard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O^{*}(1.2721^{n}) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O^{*}(2.2306^{k})time polynomialspace algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not.

