Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

DOI10.1016/J.TCS.2014.06.007zbMATH Open1417.68159OpenAlexW2011473626MaRDI QIDQ2253192FDOQ2253192

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

Recommendations

• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Algorithm Theory - SWAT 2004
• Collective tree spanners in graphs with bounded parameters
• Algorithms and Computation
• Collective additive tree spanners for circle graphs and polygonal graphs

zbMATH Keywords

approximation algorithmsgraph algorithmsbalanced separatorscollective tree spannersRobertson-Seymour's tree-decompositionspanners of bounded tree-widthtree spanner problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• The geometry of graphs and some of its algorithmic applications
• Approximate distance oracles
• Title not available (Why is that?)
• Title not available (Why is that?)
• All-Pairs Almost Shortest Paths
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• 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
• Spanners of bounded degree graphs
• Spanners for bounded tree-length graphs
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Tree spanners in planar graphs
• On sparse spanners of weighted graphs
• On the Desirability of Acyclic Database Schemes
• Graph spanners
• Additive graph spanners
• On the complexity of computing treelength
• The hardness of approximating spanner problems
• Improved Approximation for the Directed Spanner Problem
• A Separator Theorem for Chordal Graphs
• Generating Sparse 2-Spanners
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Title not available (Why is that?)
• Spanners in sparse graphs
• Compact and low delay routing labeling scheme for unit disk graphs
• 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
• Additive Tree Spanners
• Distance approximating spanning trees
• Graph-Theoretic Concepts in Computer Science
• Lower-Stretch Spanning Trees
• Title not available (Why is that?)
• Tree-decompositions with bags of small diameter
• The zoo of tree spanner problems
• An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Title not available (Why is that?)
• Approximating \(k\)-spanner problems for \(k>2\)
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• Dynamic analysis of the arrow distributed protocol
• Tree spanners for bipartite graphs and probe interval graphs
• Title not available (Why is that?)
• (1 + εΒ) -spanner constructions for general graphs
• On the hardness of approximating spanners
• Approximation of minimum weight spanners for sparse graphs
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• Title not available (Why is that?)
• Title not available (Why is that?)
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• Collective tree spanners in graphs with bounded parameters
• Directed spanners via flow-based linear programs
• Additive Spanners in Nearly Quadratic Time
• 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

Cited In (9)

• Easy computation of eccentricity approximating trees
• Algorithm Theory - SWAT 2004
• Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
• On the complexity of computing treebreadth
• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences
• Covering metric spaces by few trees
• Collective Additive Tree Spanners of Homogeneously Orderable Graphs
• Collective tree spanners for unit disk graphs with applications
• Algorithms and Computation

This page was built for publication: Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

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