How to use spanning trees to navigate in graphs
From MaRDI portal
Publication:2375948
DOI10.1007/s00453-012-9647-1zbMath1267.05254MaRDI QIDQ2375948
Publication date: 25 June 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9647-1
distances; lower bounds; graph algorithms; spanning trees; \(k\)-chordal graphs; ancestry; \(\delta\)-hyperbolic graphs; navigating in graphs; routing in graphs; tree-length \(\lambda\) graphs
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Collective additive tree spanners for circle graphs and polygonal graphs
- Local MST computation with short advice
- A faster distributed protocol for constructing a minimum spanning tree
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- A survey on interval routing
- The geometry of graphs and some of its algorithmic applications
- Tree-decompositions with bags of small diameter
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Geometric ad-hoc routing
- The small-world phenomenon
- Labelling and Implicit Routing in Networks
- Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Algorithmic Aspects of Vertex Elimination on Graphs
- Dually Chordal Graphs
- Graph Classes: A Survey
- On the power of BFS to determine a graph's diameter
- Distributed Computing: A Locality-Sensitive Approach
- Maintaining minimum spanning trees in dynamic graphs
- Distance labeling in graphs
- Proximity-preserving labeling schemes
- Reconstructing approximate tree metrics
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- Navigating in a Graph by Aid of Its Spanning Tree Metric
