Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
From MaRDI portal
Publication:2253192
DOI10.1016/j.tcs.2014.06.007zbMath1417.68159MaRDI QIDQ2253192
Feodor F. Dragan, Muad Abu-Ata
Publication date: 25 July 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.007
graph algorithms; approximation algorithms; balanced separators; collective tree spanners; Robertson-Seymour's tree-decomposition; spanners of bounded tree-width; tree spanner problem
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Easy computation of eccentricity approximating trees, On the complexity of computing treebreadth, Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \), Covering metric spaces by few trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compact and low delay routing labeling scheme for unit disk graphs
- Approximating \(k\)-spanner problems for \(k>2\)
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- Approximation of minimum weight spanners for sparse graphs
- Spanners in sparse graphs
- Collective tree spanners in graphs with bounded parameters
- Dynamic analysis of the arrow distributed protocol
- Tree spanners for bipartite graphs and probe interval graphs
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- On the complexity of computing treelength
- On sparse spanners of weighted graphs
- Low complexity variants of the arrow distributed directory
- There are planar graphs almost as good as the complete graph
- Tree spanners on chordal graphs: complexity and algorithms
- The geometry of graphs and some of its algorithmic applications
- Spanners of bounded degree graphs
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- The hardness of approximating spanner problems
- The zoo of tree spanner problems
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
- Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
- Improved Approximation for the Directed Spanner Problem
- On the Desirability of Acyclic Database Schemes
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- A Separator Theorem for Chordal Graphs
- Approximate distance oracles
- Additive Spanners in Nearly Quadratic Time
- Lower-Stretch Spanning Trees
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Graph spanners
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Generating Sparse 2-Spanners
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Additive Tree Spanners
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- All-Pairs Almost Shortest Paths
- Distance approximating spanning trees
- (1 + εΒ) -spanner constructions for general graphs
- Additive graph spanners
- Collective Tree Spanners and Routing in AT-free Related Graphs
- Directed spanners via flow-based linear programs
- Collective tree spanners of graphs
- Graph-Theoretic Concepts in Computer Science
- A tight bound on approximating arbitrary metrics by tree metrics
- Tree spanners in planar graphs
- On the hardness of approximating spanners
