Navigating in a Graph by Aid of Its Spanning Tree Metric

DOI10.1137/090761549zbMath1228.05119MaRDI QIDQ5894322

Feodor F. Dragan, Martin Matamala

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090761549

zbMATH Keywords

distances; hypercubes; chordal graphs; efficient algorithms; \(k\)-trees; dually chordal graphs; spanning trees; chordal bipartite graphs; navigating in graphs; routing in graphs; rectilinear grids

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

94C15: Applications of graph theory to circuits and networks

68W25: Approximation algorithms

Related Items

Sensitivity analysis of the proximal-based parallel decomposition methods, How to use spanning trees to navigate in graphs, On Strong Tree-Breadth