Tree spanners in planar graphs
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1262806
- scientific article; zbMATH DE number 975390
- On tree-t-spanners in graphs
- On tree-\(t\)-spanners in graphs
- Spanning trees in locally planar triangulations
- Spanners for bounded tree-length graphs
- Tree spanners of bounded degree graphs
- scientific article; zbMATH DE number 861354
- Tree spanners on chordal graphs: complexity and algorithms
- Spanning tree congestion of planar graphs
Cites work
- An Optimal Synchronizer for the Hypercube
- Delaunay graphs are almost as good as complete graphs
- Design networks with bounded pairwise distance
- Graph spanners
- Graph theory
- Grid spanners
- scientific article; zbMATH DE number 1003288 (Why is no real title available?)
- scientific article; zbMATH DE number 434498 (Why is no real title available?)
- scientific article; zbMATH DE number 1262806 (Why is no real title available?)
- scientific article; zbMATH DE number 1102774 (Why is no real title available?)
- scientific article; zbMATH DE number 1107724 (Why is no real title available?)
- scientific article; zbMATH DE number 1182768 (Why is no real title available?)
- NP-completeness of minimum spanner problems
- On sparse spanners of weighted graphs
- Planar Formulae and Their Uses
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Tree Spanners
Cited in
(50)- Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
- Planar bichromatic minimum spanning trees
- Tree spanners of bounded degree graphs
- Parameterized complexity of the spanning tree congestion problem
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Tree spanners on chordal graphs: complexity and algorithms
- Spanners of bounded degree graphs
- The minimum stretch spanning tree problem for typical graphs
- Well-partitioned chordal graphs
- Minimum \(t\)-spanners on subcubic graphs
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Tree-decompositions with bags of small diameter
- Spanners for bounded tree-length graphs
- The zoo of tree spanner problems
- Max-stretch reduction for tree spanners
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Optimality computation of the minimum stretch spanning tree problem
- Three problems on well-partitioned chordal graphs
- On approximating tree spanners that are breadth first search trees
- scientific article; zbMATH DE number 1696535 (Why is no real title available?)
- Network flow spanners
- Complexity results for the spanning tree congestion problem
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Computing geometric minimum-dilation graphs is NP-hard
- Spanning tree congestion of planar graphs
- scientific article; zbMATH DE number 1262806 (Why is no real title available?)
- scientific article; zbMATH DE number 475595 (Why is no real title available?)
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Tree Spanners
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- Plane Spanning Trees in Edge-Colored Simple Drawings of $$K_{n}$$
- Spanning tree congestion of k-outerplanar graphs
- Approximating \(k\)-spanner problems for \(k>2\)
- Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
- Better hardness results for the minimum spanning tree congestion problem
- Tree 3-spanners on generalized prisms of graphs
- Spanners in sparse graphs
- Polynomial algorithms for sparse spanners on subcubic graphs
- Better hardness results for the minimum spanning tree congestion problem
- Carousel greedy algorithms for the minimum stretch spanning tree problem
- Minimizing distances between vertices and edges through tree t-spanners
- Minimizing distances between vertices and edges through tree \(t\)-spanners
- Bicriteria approximation for minimum dilation graph augmentation
- Tree t-spanners for edge adjacency distances
- Parameterized spanning tree congestion
- Classes of cycle bases
- Tree spanners for bipartite graphs and probe interval graphs
- Computing a minimum-dilation spanning tree is NP-hard
- Combinatorial network abstraction by trees and distances
This page was built for publication: Tree spanners in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928870)
