dc.contributor |
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
dc.contributor.author |
Demaine, Erik D. |
dc.contributor.author |
Fomin, Fedor V. |
dc.contributor.author |
Hajiaghayi, Mohammad Taghi |
dc.contributor.author |
Thilikos Touloupas, Dimitrios |
dc.date |
2003-09 |
dc.identifier.citation |
Demaine, E., Fomin, F., Hajiaghayi, M., Thilikos, D. "Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs". 2003. |
dc.identifier.uri |
http://hdl.handle.net/2117/96917 |
dc.language.iso |
eng |
dc.relation |
LSI-03-43-R |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
dc.subject |
Planar graphs |
dc.subject |
Map graphs |
dc.title |
Fixed-parameter algorithms for the (k,r)-center in planar graphs and map graphs |
dc.type |
info:eu-repo/semantics/publishedVersion |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
The (k,r)-center problem} asks whether an input graph
G has atr most k vertices (called centers) such that every vertex
of $ is within distance at most r from some center. In this paper we prove that the (k,r)-center problem, parameterized by k and r, is fixed-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(rlog r) sqrt{k}}, where the exponent
of the exponential term grows sublinearly in the number of centers.
Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of map graphs introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for
graphs of small branchwidth and a graph-theoretic result bounding
this parameter in terms of k and r. Finally, a byproduct of
our algorithm is the existence of a PTAS for the r-domination
problem in both planar graphs and map graphs.
Our approach builds on the seminal results of Robertson and
Seymour on Graph Minors, and as a result is much more powerful
than the previous machinery of Alber et al. for exponential
speedup on planar graphs. To demonstrate the versatility of our
results, we show how our algorithms can be extended to general
parameters that are |