Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
verfasst von : Toshihiro Fujito
Erschienen in: Algorithm Theory – SWAT 2014
Verlag: Springer International Publishing
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
We consider a multiple domination version of the edge dominating set problem, called the
b-EDS
problem, where an edge set
D
⊆
E
of minimum cardinality is sought in a given graph
G
= (
V
,
E
) with a demand vector
b
∈ ℤ
E
such that each edge
e
∈
E
is required to be dominated by
b
(
e
) edges of
D
. When a solution
D
is not allowed to be a multi-set, it is called the
simple
b
-EDS problem. We present 2-approximation algorithms for the simple
b
-EDS problem for the cases of max
e
∈
E
b
(
e
) = 2 and max
e
∈
E
b
(
e
) = 3. The best approximation guarantee previously known for these problems is 8/3 due to Berger et al. [2] who showed the same guarantee to hold even for the minimum cost case and for arbitrarily large
b
. Our algorithms are designed based on an LP relaxation of the
b
-EDS problem and locally optimal matchings, and the optimum of
b
-EDS is related to either the size of such a matching or to the optimal LP value.