Covering Planar Graphs with a Fixed Number of Balls |
| |
| Authors: | Victor Chepoi Bertrand Estellon Yann Vaxes |
| |
| Affiliation: | (1) Laboratoire d'Informatique Fondamentale de Marseille, Faculte des Sciences de Luminy, Universite de la Mediterranee, F-13288, Marseille Cedex 9, France |
| |
| Abstract: | In this note we prove that there exists a constant ρ such that any planar graph G of diameter ≤ 2R can be covered with at most ρ balls of radius R, a result conjectured by Gavoille, Peleg, Raspaud, and Sopena in 2001. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
