Advertisement
Published in:
2006 | OriginalPaper | Chapter
Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
Authors : Daniel Mölle, Stefan Richter, Peter Rossmanith
Published in: Computer Science – Theory and Applications
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
We present a new method of solving graph problems related to
VERTEX COVER
by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the
VERTEX COVER
problem: In the case of
CONNECTED VERTEX COVER
, we take the upper bound from
O
*
(6
k
) to
O
*
(3.2361
k
) without large hidden factors. For
TREE COVER
, we show exactly the same complexity, improving vastly over the previous bound of
O
*
((2
k
)
k
). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.