A 2-approximation NC algorithm for connected vertex cover and tree cover

DOI10.1016/j.ipl.2004.01.011zbMath1178.68377MaRDI QIDQ2390219

Toshihiro Fujito, Takashi Doi

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.01.011

zbMATH Keywords

parallel algorithms; approximation algorithms; connected vertex cover; tree cover

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms