Navigating in a Graph by Aid of Its Spanning Tree Metric

DOI10.1137/090761549zbMath1228.05119OpenAlexW1994320209MaRDI 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

distanceshypercubeschordal graphsefficient algorithms\(k\)-treesdually chordal graphsspanning treeschordal bipartite graphsnavigating in graphsrouting in graphsrectilinear grids

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Approximation algorithms (68W25)

Related Items (3)

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

This page was built for publication: Navigating in a Graph by Aid of Its Spanning Tree Metric