Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
verfasst von : Andreas Brandstädt, Arne Leitert, Dieter Rautenbach
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
= (
V
,
E
) be a graph. A vertex
dominates
itself and all its neighbors, i.e., every vertex
v
∈
V
dominates its closed neighborhood
N
[
v
]. A vertex set
D
in
G
is an
efficient dominating
(
e.d.
) set for
G
if for every vertex
v
∈
V
, there is exactly one
d
∈
D
dominating
v
. An edge set
M
⊆
E
is an
efficient edge dominating
(
e.e.d.
) set for
G
if it is an efficient dominating set in the line graph
L
(
G
) of
G
. The ED problem (EED problem, respectively) asks for the existence of an e.d. set (e.e.d. set, respectively) in the given graph.
We give a unified framework for investigating the complexity of these problems on various classes of graphs. In particular, we solve some open problems and give linear time algorithms for ED and EED on dually chordal graphs.
We extend the two problems to hypergraphs and show that ED remains
$\mathbb{NP}$
-complete on
α
-acyclic hypergraphs, and is solvable in polynomial time on hypertrees, while EED is polynomial on
α
-acyclic hypergraphs and
$\mathbb{NP}$
-complete on hypertrees.