Geodesic
Optimal Data Structures for Farthest-Point Queries in Cactus Networks
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 11-41.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Consider the continuum of points on the edges of a network, i.e., a connected, undirected graph with positive edge weights. We measure the distance between these points in terms of the weighted shortest path distance, called the network distance. Within this metric space, we study farthest points and farthest distances. We introduce optimal data structures supporting queries for the farthest distance and the farthest points on trees, cycles, uni-cyclic networks, and cactus networks. Using only linear space and construction time, we support farthest-point queries in Θ(k) time for trees, in Θ(logn) time for cycles, and in Θ(k + logn) time for uni-cyclic networks and cactus networks, where n is the size of the network and k is the number of farthest-points. 
@article{JGAA_2015_19_1_a1,
     author = {Prosenjit Bose and Jean-Lou De Carufel and Carsten Grimm and Anil Maheshwari and Michiel Smid},
     title = {Optimal {Data} {Structures} for {Farthest-Point} {Queries} in {Cactus} {Networks}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {11--41},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00345},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00345/}
}
TY  - JOUR
AU  - Prosenjit Bose
AU  - Jean-Lou De Carufel
AU  - Carsten Grimm
AU  - Anil Maheshwari
AU  - Michiel Smid
TI  - Optimal Data Structures for Farthest-Point Queries in Cactus Networks
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 11
EP  - 41
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00345/
DO  - 10.7155/jgaa.00345
LA  - en
ID  - JGAA_2015_19_1_a1
ER  - 
%0 Journal Article
%A Prosenjit Bose
%A Jean-Lou De Carufel
%A Carsten Grimm
%A Anil Maheshwari
%A Michiel Smid
%T Optimal Data Structures for Farthest-Point Queries in Cactus Networks
%J Journal of Graph Algorithms and Applications
%D 2015
%P 11-41
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00345/
%R 10.7155/jgaa.00345
%G en
%F JGAA_2015_19_1_a1
Prosenjit Bose; Jean-Lou De Carufel; Carsten Grimm; Anil Maheshwari; Michiel Smid. Optimal Data Structures for Farthest-Point Queries in Cactus Networks. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 11-41. doi : 10.7155/jgaa.00345. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00345/

Cité par Sources :