Collective tree spanners of graphs

DOI10.1137/S089548010444167XMaRDI QIDQ5470830zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan, Chenyu Yan, Irina Lomonosov

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

\(c\)-chordal graphsbalanced separatorchordal graphsefficient algorithmsgraph decompositiongraph distancemessage routingsparse spanners

Mathematics Subject Classification ID

Trees (05C05) 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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Algorithm Theory - SWAT 2004
• Collective tree spanners in graphs with bounded parameters
• Algorithms and Computation
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Graph-Theoretic Concepts in Computer Science

Cited in

(25)

• Easy computation of eccentricity approximating trees
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Collective tree spanners for unit disk graphs with applications
• On advice complexity of the k-server problem under sparse metrics
• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Interval routing schemes for circular-arc graphs
• Synchronous rendezvous for location-aware agents
• Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
• Navigating in a Graph by Aid of Its Spanning Tree
• Compact and low delay routing labeling scheme for unit disk graphs
• Collective additive tree spanners for circle graphs and polygonal graphs
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Algorithm Theory - SWAT 2004
• Notes on the Distributed Computation of Merge Trees on CW-Complexes
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• Graph-Theoretic Concepts in Computer Science
• Navigating in a graph by aid of its spanning tree metric
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation
• Optimal Euclidean tree covers
• Optimal Euclidean tree covers
• Collective tree spanners in graphs with bounded parameters

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

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