For Full-Text 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.
An Exact Algorithm for Lowest Edge Dominating Set
Ken IWAIDE Hiroshi NAGAMOCHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2017/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
graph theory, edge dominating set, algorithm, NP-completeness, fixed parameter tractable,
Full Text: PDF(304.7KB)>>
Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size µ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size ⌈µ(G)/2⌉ or not. In this paper, we prove that the problem is NP-complete, whereas we design an O*(2.0801µ(G)/2)-time and polynomial-space algorithm to the problem.