2006 | OriginalPaper | Chapter
Flexible Matchings
Authors : Miklós Bartha, Miklós Krész
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A matching
M
is called flexible if there exists an alternating cycle with respect to
M
. Given a graph
G
=(
V
,
E
) and
S
⊆
V
, a flexible matching
M
⊆
E
is sought which covers a maximum number of vertices belonging to
S
. It is proved that the existence of such a matching is decidable in
$\mathcal{O}(|V|\cdot |E|)$
time, and a concrete flexible maximum
S
-matching can also be found in the same amount of time.