Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover |
| |
Authors: | Daniel Mölle Stefan Richter Peter Rossmanith |
| |
Affiliation: | (1) Dept. of Comp. Sci., RWTH Aachen University, Aachen, Germany |
| |
Abstract: | 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
*(2.7606
k
) without large hidden factors. For Tree Cover, we show a complexity of O
*(3.2361
k
), improving over the previous bound of O
*((2k)
k
). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.
Supported by the DFG under grant RO 927/6-1 (TAPI). |
| |
Keywords: | Exact algorithms Parameterized complexity Enumerate and expand Vertex cover |
本文献已被 SpringerLink 等数据库收录! |
|