Collective tree spanners in graphs with bounded parameters

DOI10.1007/S00453-008-9194-YzbMATH Open1223.05247OpenAlexW2016638039MaRDI QIDQ848633FDOQ848633

Chenyu Yan, Feodor F. Dragan

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

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

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)

Cites Work

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

Cited In (10)

• A general lower bound for collaborative tree exploration
• Algorithm Theory - SWAT 2004
• 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
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Distance and routing labeling schemes for cube-free median graphs
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• Graph-Theoretic Concepts in Computer Science
• Collective tree spanners for unit disk graphs with applications
• Optimal centrality computations within bounded clique-width 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)