Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Simultaneous Matchings
verfasst von : Khaled Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan
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
Given a bipartite graph
$G = (X \dot{\cup} D,E \subseteq X \times D)$
, an
X-perfect matching
is a matching in
G
that covers every node in
X
. In this paper we study the following generalisation of the
X
-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection
$\mathcal{F} \subseteq 2^{X}$
of
k
subsets of
X
, find a subset
M
⊆
E
of the edges such that for each
$C \in \mathcal{F}$
, the edge set
M
∩ (
C
×
D
) is a
C
-perfect matching in
G
(or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when
k
=
O
(1) and even APX-complete already for
k
=2. On the positive side, we show that a 2/(
k
+1)-approximation can be found in 2
k
poly(
k
,|
X
∪
D
|) time.