How to use spanning trees to navigate in graphs

DOI10.1007/S00453-012-9647-1MaRDI QIDQ2375948zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Yang Xiang

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

zbMATH Keywords

distancesspanning treeslower boundsgraph algorithms\(k\)-chordal graphsancestry\(\delta\)-hyperbolic graphsnavigating in graphsrouting in graphstree-length \(\lambda\) graphs

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12)

Recommendations

• How to Use Spanning Trees to Navigate in Graphs
• Navigating in a Graph by Aid of Its Spanning Tree
• Navigating in a graph by aid of its spanning tree metric
• Using a Significant Spanning Tree to Draw a Directed Graph
• scientific article; zbMATH DE number 1424297
• Good spanning trees in graph drawing
• scientific article; zbMATH DE number 3908451
• Spanning paths in graphs
• Spanning tree of a multiple graph
• scientific article; zbMATH DE number 1533198

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 1875437 (Why is no real title available?)
• scientific article; zbMATH DE number 849252 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A faster distributed protocol for constructing a minimum spanning tree
• A survey on interval routing
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Collective additive tree spanners for circle graphs and polygonal graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Distance labeling in graphs
• Distributed Computing: A Locality-Sensitive Approach
• Dually Chordal Graphs
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• Geometric ad-hoc routing
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Labelling and Implicit Routing in Networks
• Local MST computation with short advice
• Maintaining minimum spanning trees in dynamic graphs
• Navigating in a graph by aid of its spanning tree metric
• On the power of BFS to determine a graph's diameter
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Proximity-preserving labeling schemes
• Reconstructing approximate tree metrics
• Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
• 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
• The geometry of graphs and some of its algorithmic applications
• The small-world phenomenon: an algorithmic perspective
• Tree-decompositions with bags of small diameter

Cited in

(4)

• Navigating in a graph by aid of its spanning tree metric
• scientific article; zbMATH DE number 742889 (Why is no real title available?)
• How to Use Spanning Trees to Navigate in Graphs
• Navigating in a Graph by Aid of Its Spanning Tree

This page was built for publication: How to use spanning trees to navigate in graphs

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