Lokshtanov, Daniel ; Narayanaswamy, N. S. ; Raman, Venkatesh ; Ramanujan, M. S. ; Saurabh, Saket (2014) Faster Parameterized Algorithms Using Linear Programming ACM Transactions on Algorithms, 11 (2). pp. 1-31. ISSN 1549-6325
Full text not available from this repository.
Official URL: http://doi.org/10.1145/2566616
Related URL: http://dx.doi.org/10.1145/2566616
Abstract
We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O*(2.618k) algorithm for the problem. Here, k is the excess of the vertex cover size over the LP optimum, and we write O*(f(k)) for a time complexity of the form O(f(k)nO(1)). We proceed to show that a more sophisticated branching algorithm achieves a running time of O*(2.3146k).
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Association for Computing Machinery. |
| ID Code: | 123427 |
| Deposited On: | 16 Sep 2021 10:46 |
| Last Modified: | 16 Sep 2021 10:46 |
Repository Staff Only: item control page
