Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems |
| |
Authors: | Jianer Chen Iyad A Kanj Ge Xia |
| |
Affiliation: | (1) Department of Computer Science, Texas A&M University, College Station, TX 77843-3112, USA;(2) School of CTI, DePaul University, 243 S. Wabash Avenue, Chicago, IL 60604-2301, USA |
| |
Abstract: | A sequence of exact algorithms to solve the Vertex Cover and
Maximum Independent Set problems have been proposed in the
literature. All these algorithms appeal to a very conservative
analysis that considers the size of the search tree, under a
worst-case scenario, to derive an upper bound on the running time
of the algorithm. In this paper we propose a different approach to
analyze the size of the search tree. We use amortized analysis to
show how simple algorithms, if analyzed properly, may perform much
better than the upper bounds on their running time derived by
considering only a worst-case scenario. This approach allows us to
present a simple algorithm of running time O(1.194kk2 + n)
for the parameterized Vertex Cover problem on degree-3
graphs, and a simple algorithm of running time O(1.1255n) for
the Maximum Independent Set problem on degree-3 graphs.
Both algorithms improve the previous best algorithms for the
problems. |
| |
Keywords: | Vertex cover Independent set Exact algorithm Parameterized algorithm |
本文献已被 SpringerLink 等数据库收录! |
|