Premium
Algorithms for finding P‐centers on a weighted tree (for relatively small P)
Author(s) -
Jeger M.,
Kariv O.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150308
Subject(s) - combinatorics , vertex (graph theory) , binary logarithm , center (category theory) , mathematics , range (aeronautics) , tree (set theory) , log log plot , algorithm , graph , chemistry , materials science , composite material , crystallography
Algorithms of O(p. n . log n ) time to find an (absolute or vertex) p ‐center on a weighted tree of n vertices are presented. Those algorithms represent improvement over previous known results in the range p < log n (for the vertex p ‐center problem) and in the range p < log n . log log n (for the absolute p ‐center problem).