In *Proc. of Mathematical Foundations of Computer Science (MFCS 2006)*, volume 4162, of *Lect Notes Comput Sci*, pages 238–249, 2006.

doi abstract bibtex

doi abstract bibtex

This paper presents an O(1.2738^k + kn)-time polynomial-space parameterized algorithm for Vertex Cover improving the previous O(1.286^k + kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. The algorithm also improves the O(1.2745^k k^4 + kn)-time exponential-space upper bound for the problem by Chandran and Grandoni.

@InProceedings{chen06improved-parameterized, author = {Jianer Chen and Iyad A. Kanj and Ge Xia}, title = {Improved Parameterized Upper Bounds for Vertex Cover}, booktitle = {Proc. of Mathematical Foundations of Computer Science (MFCS 2006)}, year = {2006}, volume = {4162}, series = lncs, pages = {238--249}, publisher = Springer, abstract = {This paper presents an O(1.2738^k + kn)-time polynomial-space parameterized algorithm for Vertex Cover improving the previous O(1.286^k + kn)-time polynomial-space upper bound by Chen, Kanj, and Jia. The algorithm also improves the O(1.2745^k k^4 + kn)-time exponential-space upper bound for the problem by Chandran and Grandoni.}, doi = {10.1007/11821069_21}, }

Downloads: 0