Spanners in sparse graphs
From MaRDI portal
Publication:657919
DOI10.1016/j.jcss.2010.10.002zbMath1234.68149WikidataQ60488576 ScholiaQ60488576MaRDI QIDQ657919
Petr A. Golovach, Fedor V. Fomin, Feodor F. Dragan
Publication date: 11 January 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.10.002
distance in graphs; planar graphs; treewidth; graph algorithms; spanners; parametrized complexity; apex-minor-free graphs
68Q25: Analysis of algorithms and problem complexity
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Better hardness results for the minimum spanning tree congestion problem, Tree 3-spanners on generalized prisms of graphs, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Tree \(t\)-spanners in outerplanar graphs via supply demand partition, Graph spanners: a tutorial review, Hardness and efficiency on minimizing maximum distances in spanning trees, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Subexponential parameterized algorithms
- Approximating \(k\)-spanner problems for \(k>2\)
- Tree spanners for bipartite graphs and probe interval graphs
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- Linearity of grid minors in treewidth with applications through bidimensionality
- On problems without polynomial kernels
- Call routing and the ratcatcher
- Quickly excluding a planar graph
- A simpler proof of the excluded minor theorem for higher surfaces
- Graph minors. XVI: Excluding a non-planar graph
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Embedding grids in surfaces
- Tree spanners on chordal graphs: complexity and algorithms
- The geometry of graphs and some of its algorithmic applications
- The hardness of approximating spanner problems
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Competitive concurrent distributed queuing
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Spanners in Sparse Graphs
- Approximate distance oracles
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Lower-Stretch Spanning Trees
- Contraction Bidimensionality: The Accurate Picture
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Graph spanners
- Planar Formulae and Their Uses
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Generating Sparse 2-Spanners
- Handbook of Graph Grammars and Computing by Graph Transformation
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- (Meta) Kernelization
- Bidimensional Parameters and Local Treewidth
- Bidimensionality and Geometric Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A tight bound on approximating arbitrary metrics by tree metrics
- Tree spanners in planar graphs
- On the hardness of approximating spanners
