Collective tree spanners of graphs

DOI10.1137/S089548010444167XzbMath1112.05025OpenAlexW2093095561MaRDI QIDQ5470830

Irina Lomonosov, Feodor F. Dragan, Chenyu Yan

Publication date: 1 June 2006

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

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

zbMATH Keywords

chordal graphsgraph decompositionefficient algorithmsgraph distancemessage routingsparse spannersbalanced separator\(c\)-chordal graphs

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 (14)

Collective tree spanners in graphs with bounded parameters ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs ⋮ Compact and low delay routing labeling scheme for unit disk graphs ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ Easy computation of eccentricity approximating trees ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Collective Additive Tree Spanners of Homogeneously Orderable Graphs ⋮ Synchronous Rendezvous for Location-Aware Agents ⋮ Collective Tree Spanners for Unit Disk Graphs with Applications ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics

This page was built for publication: Collective tree spanners of graphs