Optimal Data Structures for Farthest-Point Queries in Cactus Networks

DOI10.7155/JGAA.00345MaRDI QIDQ2940594zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Michiel Smid

Publication date 27 January 2015

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1411.1879

zbMATH Keywords

network distanceoptimal data structures

Mathematics Subject Classification ID

Distance in graphs (05C12) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks
• Efficient algorithms for center problems in cactus networks
• Fast searching on cactus graphs
• Farthest-point queries with geometric and combinatorial constraints
• Farthest-Point Queries with Geometric and Combinatorial Constraints
• Optimal nearest neighbor queries in sensor networks
• Optimal nearest neighbor queries in sensor networks
• scientific article; zbMATH DE number 2166874

Cited in

(2)

• Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks
• Network farthest-point diagrams

Describes a project that uses

Uses Software

• Algorithm 447
• SANET

This page was built for publication: Optimal Data Structures for Farthest-Point Queries in Cactus Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2940594)