Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Fast Approximation Algorithms for p-centers in Large \(\delta \)-hyperbolic Graphs
verfasst von : Katherine Edwards, Sean Kennedy, Iraj Saniee
Erschienen in: Algorithms and Models for the Web Graph
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \(\delta \), we construct an algorithm for p-centers in time \(O(p(\delta +1)(n+m)\log _2(n))\) with radius not exceeding \(r_p + \delta \) when \(p \le 2\) and \(r_p + 3\delta \) when \(p \ge 3\), where \(r_p\) are the optimal radii. Prior work identified p-centers with accuracy \(r_p+\delta \) but with time complexity \(O((n^3\log _2 n + n^2m)\log _2({{\mathrm{diam}}}(G)))\) which is impractical for large graphs.