A simple local 3-approximation algorithm for vertex cover |
| |
| Authors: | Valentin Polishchuk |
| |
| Affiliation: | Helsinki Institute for Information Technology HIIT, Helsinki University of Technology and University of Helsinki, PO Box 68, FI-00014 University of Helsinki, Finland |
| |
| Abstract: | We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. |
| |
| Keywords: | Approximation algorithms Distributed computing Graph algorithms Local algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
