Fast Approximation Algorithms for p-Centers in Large ? -Hyperbolic Graphs

© 2018, Springer Science+Business Media, LLC, part of Springer Nature. We provide a quasilinear time algorithm for the p-center problem with an additive error less than or equal to 3 times the input graph?s hyperbolic constant. Specifically, for the graph G= (V, E) with n vertices, m edges and hyperbolic constant ?, we construct an algorithm for p-centers in time O(p(?+ 1) (n+ m) log (n)) with radius not exceeding rp+ ? when p? 2 and rp+ 3 ? when p? 3 , where rp are the optimal radii. Prior work identified p-centers with accuracy rp+ ? but with time complexity O((n3log n+ n2m) log (diam (G))) which is impractical for large graphs.