Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Efficient Algorithms for the 2-Center Problems
verfasst von : Tadao Takaoka
Erschienen in: Computational Science and Its Applications – ICCSA 2010
Verlag: Springer Berlin Heidelberg
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
This paper achieves
O
(
n
3
loglog
n
/log
n
) time for the 2-center problems on a directed graph with non-negative edge costs under the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with
O
(log
n
) bits are allowed. Here
n
is the number of vertices. This is a slight improvement on the best known complexity of those problems, which is
O
(
n
3
). We further show that when the graph is with unit edge costs, one of the 2-center problems can be solved in
O
(
n
2.575
) time.