Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00224-007-9089-3 | Theory of Computing Systems \/ Mathematical Systems Theory |
Keywords | Field | DocType |
Exact algorithms,Parameterized complexity,Enumerate and expand,Vertex cover | Discrete mathematics,Combinatorics,Prim's algorithm,Vertex (graph theory),Edge cover,Steiner tree problem,Computer science,Algorithm,Neighbourhood (graph theory),Vertex separator,Vertex cover,Feedback vertex set | Journal |
Volume | Issue | ISSN |
43 | 2 | 1432-4350 |
Citations | PageRank | References |
23 | 1.06 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Mölle | 1 | 175 | 10.17 |
| Stefan Richter | 2 | 176 | 9.96 |
| Peter Rossmanith | 3 | 1000 | 61.03 |