Spanners in sparse graphs
From MaRDI portal
Publication:657919
Recommendations
Cites work
- scientific article; zbMATH DE number 1375574 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1559591 (Why is no real title available?)
- scientific article; zbMATH DE number 1929927 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- (Meta) Kernelization
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- A simpler proof of the excluded minor theorem for higher surfaces
- A tight bound on approximating arbitrary metrics by tree metrics
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Approximate distance oracles
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Approximating \(k\)-spanner problems for \(k>2\)
- Bidimensional Parameters and Local Treewidth
- Bidimensionality and kernels
- Call routing and the ratcatcher
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Competitive concurrent distributed queuing
- Contraction Bidimensionality: The Accurate Picture
- Embedding grids in surfaces
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Generating Sparse 2-Spanners
- Graph minors. XVI: Excluding a non-planar graph
- Graph spanners
- Graphs on surfaces
- Handbook of Graph Grammars and Computing by Graph Transformation
- Linearity of grid minors in treewidth with applications through bidimensionality
- Lower-Stretch Spanning Trees
- On problems without polynomial kernels
- On the hardness of approximating spanners
- Parametrized complexity theory.
- Planar Formulae and Their Uses
- Quickly excluding a planar graph
- Spanners in Sparse Graphs
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- The geometry of graphs and some of its algorithmic applications
- The hardness of approximating spanner problems
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- Tree Spanners
- Tree spanners for bipartite graphs and probe interval graphs
- Tree spanners in planar graphs
- Tree spanners on chordal graphs: complexity and algorithms
Cited in
(25)- Polynomial algorithms for sparse spanners on subcubic graphs
- Spanners in Sparse Graphs
- Approximation of minimum weight spanners for sparse graphs
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- On Pairwise Spanners
- Spanners of bounded degree graphs
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Sparsity. Graphs, structures, and algorithms
- Sparsification lower bound for linear spanners in directed graphs
- Spanning with indexes
- Spanners for Geometric Intersection Graphs
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- Graph spanners
- Additive graph spanners
- Graph spanners: a tutorial review
- Relaxed Spanners for Directed Disk Graphs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Tree 3-spanners on generalized prisms of graphs
- Almost All Even Yao-Yao Graphs Are Spanners
- Hardness and efficiency on minimizing maximum distances in spanning trees
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- scientific article; zbMATH DE number 1301100 (Why is no real title available?)
- Better hardness results for the minimum spanning tree congestion problem
- Better hardness results for the minimum spanning tree congestion problem
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
This page was built for publication: Spanners in sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657919)
