Vertex Cover: Further observations and further improvements Academic Article

abstract

• Recently, there has been increasing interest and progress in lowering the worst-case time complexity for well-known NP-hard problems, particularly for the VERTEX COVER problem. In this paper, new properties for the VERTEX COVER problem are indicated, and several simple and new techniques are introduced, which lead to an improved algorithm of time O(kn + 1.2852k) for the problem. Our algorithm also induces improvement on previous algorithms for the INDEPENDENT SET problem on graphs of small degree. 2001 Elsevier Science.

authors

• Chen, Jianer

published proceedings

• JOURNAL OF ALGORITHMS

altmetric score

• 3

author list (cited authors)

• Chen, J., Kanj, I. A., & Jia, W. J.

citation count

• 294

complete list of authors

• Chen, J||Kanj, IA||Jia, WJ

publication date

• November 2001

publisher

• Elsevier  Publisher

published in

• Journal of Algorithms in Cognition, Informatics and Logic  Journal

Digital Object Identifier (DOI)

• 10.1006/jagm.2001.1186

start page

• 280

end page

• 301

volume

• 41

issue

• 2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1006%2Fjagm.2001.1186