Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems Academic Article

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.1255 n) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems. 2005 Springer Science+Business Media Inc.

authors

• Chen, Jianer

published proceedings

• Algorithmica

author list (cited authors)

• Chen, J., Kanj, I. A., & Xia, G. e.

citation count

• 29

complete list of authors

• Chen, Jianer||Kanj, Iyad A||Xia, Ge

publication date

• December 2005

publisher

• Springer Nature  Publisher

published in

• Algorithmica: an international journal in computer science  Journal

keywords

• 46 Information And Computing Sciences
• 4602 Artificial Intelligence
• 49 Mathematical Sciences
• 4901 Applied Mathematics
• 4904 Pure Mathematics
• Bioengineering
• Pediatric

Digital Object Identifier (DOI)

• 10.1007/s00453-004-1145-7

start page

• 245

end page

• 273

volume

• 43

issue

• 4

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2Fs00453-004-1145-7