Improved Parameterized Upper Bounds for Vertex Cover

Improved Parameterized Upper Bounds for Vertex Cover. Chen, J., Kanj, I. A., & Xia, G. In Proc. of Mathematical Foundations of Computer Science (MFCS 2006), volume 4162, of Lect Notes Comput Sci, pages 238–249, 2006. Springer, Berlin.
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

{"_id":"dFA3x6J4TyRWmhAQ3","bibbaseid":"chen-kanj-xia-improvedparameterizedupperboundsforvertexcover-2006","authorIDs":[],"author_short":["Chen, J.","Kanj, I. A.","Xia, G."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Jianer"],"propositions":[],"lastnames":["Chen"],"suffixes":[]},{"firstnames":["Iyad","A."],"propositions":[],"lastnames":["Kanj"],"suffixes":[]},{"firstnames":["Ge"],"propositions":[],"lastnames":["Xia"],"suffixes":[]}],"title":"Improved Parameterized Upper Bounds for Vertex Cover","booktitle":"Proc. of Mathematical Foundations of Computer Science (MFCS 2006)","year":"2006","volume":"4162","series":"Lect Notes Comput Sci","pages":"238–249","publisher":"Springer, Berlin","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","bibtex":"@InProceedings{chen06improved-parameterized,\n author = {Jianer Chen and Iyad A. Kanj and Ge Xia},\n title = {Improved Parameterized Upper Bounds for Vertex Cover},\n booktitle = {Proc. of Mathematical Foundations of Computer Science (MFCS 2006)},\n year = {2006},\n volume = {4162},\n series = lncs,\n pages = {238--249},\n publisher = Springer,\n 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.},\n doi = {10.1007/11821069_21},\n}\n\n","author_short":["Chen, J.","Kanj, I. A.","Xia, G."],"key":"chen06improved-parameterized","id":"chen06improved-parameterized","bibbaseid":"chen-kanj-xia-improvedparameterizedupperboundsforvertexcover-2006","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:41.727Z","downloads":0,"keywords":[],"search_terms":["improved","parameterized","upper","bounds","vertex","cover","chen","kanj","xia"],"title":"Improved Parameterized Upper Bounds for Vertex Cover","year":2006,"dataSources":["C5FtkvWWggFfMJTFX"]}