Collective tree spanners in graphs with bounded parameters

DOI10.1007/S00453-008-9194-YMaRDI QIDQ848633zbMATHOpenAlexFDO

Authors Feodor F. Dragan, Chenyu Yan

Publication date 4 March 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9194-y

zbMATH Keywords

Graph decompositionSpannersTree-widthEfficient algorithms\(c\)-Chordal graphsBalanced separatorClique-widthGraph distanceMessage routingPlanar graphsTree spanners

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Recommendations

• Algorithms and Computation
• Algorithm Theory - SWAT 2004
• Collective tree spanners of graphs
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3970774 (Why is no real title available?)
• scientific article; zbMATH DE number 2011848 (Why is no real title available?)
• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Separator Theorem for Chordal Graphs
• A Separator Theorem for Planar Graphs
• A separator theorem for graphs of bounded genus
• Additive Tree Spanners
• Additive graph spanners
• Algorithms and Computation
• An Optimal Synchronizer for the Hypercube
• Approximating \(k\)-spanner problems for \(k>2\)
• Approximating minimum MAX-stretch spanning trees on unweighted graphs
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Collective tree spanners of graphs
• Distributed Computing
• Graph minors. II. Algorithmic aspects of tree-width
• Graph spanners
• Graph-Theoretic Concepts in Computer Science
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• LexBFS-orderings and powers of chordal graphs
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• On the Problem of Partitioning Planar Graphs
• SOFSEM 2005: Theory and Practice of Computer Science
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• Tree Spanners
• Treewidth. Computations and approximations
• Upper bounds to the clique width of graphs

Cited in

(16)

• Optimal centrality computations within bounded clique-width graphs
• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Graph-Theoretic Concepts in Computer Science
• Algorithm Theory - SWAT 2004
• Collective additive tree spanners for circle graphs and polygonal graphs
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• A general lower bound for collaborative tree exploration
• Algorithms and Computation
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Collective tree spanners of graphs
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Graph-Theoretic Concepts in Computer Science
• Collective tree spanners for unit disk graphs with applications
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Distance and routing labeling schemes for cube-free median graphs

This page was built for publication: Collective tree spanners in graphs with bounded parameters

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