Fixed-parameter algorithms for the (k; r)- center in planar graphs and map graphs
| Author(s) : | Mohammadtaghi Hajiaghayi Fedor V. Fomin Erik D. Demaine Dimitrios M. Thilikos, |
| Publisher : | N/A |
| Publication Date : | 2003 |
| ISSN : | N/A |
| Abstract : | The (k; r)-center problem asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. In this paper we prove that the (k; r)-center problem, parameterized by k and r, is xed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity f(k; r)n O(1) where the function f is independent of n. In particular, we show that f(k; r) = 2 O(r log r) p, |