Spanners in sparse graphs
From MaRDI portal
Publication:657919
DOI10.1016/J.JCSS.2010.10.002zbMATH Open1234.68149OpenAlexW1980466385WikidataQ60488576 ScholiaQ60488576MaRDI QIDQ657919FDOQ657919
Authors: Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach 
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
Recommendations
treewidthgraph algorithmsplanar graphsparametrized complexityspannersdistance in graphsapex-minor-free graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On problems without polynomial kernels
- Call routing and the ratcatcher
- The geometry of graphs and some of its algorithmic applications
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graphs on surfaces
- Approximate distance oracles
- Planar Formulae and Their Uses
- Title not available (Why is that?)
- Title not available (Why is that?)
- A tight bound on approximating arbitrary metrics by tree metrics
- Quickly excluding a planar graph
- Tree spanners on chordal graphs: complexity and algorithms
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Title not available (Why is that?)
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- (Meta) Kernelization
- Bidimensionality and kernels
- Tree spanners in planar graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Handbook of Graph Grammars and Computing by Graph Transformation
- Graph spanners
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The hardness of approximating spanner problems
- Contraction Bidimensionality: The Accurate Picture
- Generating Sparse 2-Spanners
- Subexponential parameterized algorithms
- Graph minors. XVI: Excluding a non-planar graph
- Linearity of grid minors in treewidth with applications through bidimensionality
- Title not available (Why is that?)
- Spanners in Sparse Graphs
- Bidimensional Parameters and Local Treewidth
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- A trade-off between space and efficiency for routing tables
- Lower-Stretch Spanning Trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximating \(k\)-spanner problems for \(k>2\)
- Tree spanners for bipartite graphs and probe interval graphs
- A simpler proof of the excluded minor theorem for higher surfaces
- Competitive concurrent distributed queuing
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- On the hardness of approximating spanners
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- Embedding grids in surfaces
- Combinatorial Local Planarity and the Width of Graph Embeddings
Cited In (25)
- Graph spanners
- Graph spanners: a tutorial review
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- Spanning with indexes
- Almost All Even Yao-Yao Graphs Are Spanners
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Tree 3-spanners on generalized prisms of graphs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Sparsity. Graphs, structures, and algorithms
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Additive graph spanners
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Relaxed Spanners for Directed Disk Graphs
- Better hardness results for the minimum spanning tree congestion problem
- Spanners of bounded degree graphs
- Polynomial algorithms for sparse spanners on subcubic graphs
- Hardness and efficiency on minimizing maximum distances in spanning trees
- Approximation of minimum weight spanners for sparse graphs
- Sparsification lower bound for linear spanners in directed graphs
- On Pairwise Spanners
- Better hardness results for the minimum spanning tree congestion problem
- Spanners in Sparse Graphs
- Spanners for Geometric Intersection Graphs
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Title not available (Why is that?)
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)
