An Exact Algorithm for Lowest Edge Dominating Set

Ken IWAIDE; Hiroshi NAGAMOCHI

doi:10.1587/transinf.2016FCP0005

An Exact Algorithm for Lowest Edge Dominating Set

Ken IWAIDE, Hiroshi NAGAMOCHI

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.3 pp.414-421

Publication Date: 2017/03/01

Publicized: 2016/12/21

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2016FCP0005

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)

Category

Authors

Ken IWAIDE
Kyoto University
Hiroshi NAGAMOCHI
Kyoto University

Keyword

graph theory, edge dominating set, algorithm, NP-completeness, fixed parameter tractable

Cite this

Copy

Ken IWAIDE, Hiroshi NAGAMOCHI, "An Exact Algorithm for Lowest Edge Dominating Set" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 3, pp. 414-421, March 2017, doi: 10.1587/transinf.2016FCP0005.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2016FCP0005/_p

Copy

@ARTICLE{e100-d_3_414,
author={Ken IWAIDE, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={An Exact Algorithm for Lowest Edge Dominating Set},
year={2017},
volume={E100-D},
number={3},
pages={414-421},
abstract={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.},
keywords={},
doi={10.1587/transinf.2016FCP0005},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - An Exact Algorithm for Lowest Edge Dominating Set
T2 - IEICE TRANSACTIONS on Information
SP - 414
EP - 421
AU - Ken IWAIDE
AU - Hiroshi NAGAMOCHI
PY - 2017
DO - 10.1587/transinf.2016FCP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2017
AB - 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.
ER -