Tree Spanners
From MaRDI portal
Publication:4847362
DOI10.1137/S0895480192237403zbMATH Open0832.05037OpenAlexW2912257407WikidataQ30052585 ScholiaQ30052585MaRDI QIDQ4847362FDOQ4847362
Authors: Leizhen Cai, Derek G. Corneil 
Publication date: 20 September 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480192237403
Recommendations
Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)
Cited In (95)
- The zoo of tree spanner problems
- An improved algorithm for computing all the best swap edges of a tree spanner
- On spanning 2-trees in a graph
- Graph spanners: a tutorial review
- Parameterized complexity of the spanning tree congestion problem
- Spanning tree congestion of \(k\)-outerplanar graphs
- Minimum weight Euclidean \(t\)-spanner is NP-hard
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- Lower bounds on treespan
- On approximating tree spanners that are breadth first search trees
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Approximating minimum MAX-stretch spanning trees on unweighted graphs
- General variable neighborhood search for the minimum stretch spanning tree problem
- Spanners in sparse graphs
- Optimal tree 3-spanners in directed path graphs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Collective tree spanners in graphs with bounded parameters
- The minimum stretch spanning tree problem for typical graphs
- Distance Approximating Trees: Complexity and Algorithms
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Tree spanners in planar graphs
- The non-approximability of bicriteria network design problems
- On tree-\(t\)-spanners in graphs
- On tree-\(t\)-spanners in graphs
- Distance approximating spanning trees
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Complexity results for the spanning tree congestion problem
- A Faster Computation of All the Best Swap Edges of a Tree Spanner
- Additive Spanners for Circle Graphs and Polygonal Graphs
- Collective additive tree spanners for circle graphs and polygonal graphs
- An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
- Title not available (Why is that?)
- Low complexity variants of the arrow distributed directory
- NP-completeness of minimum spanner problems
- Tree spanners of bounded degree graphs
- Optimality computation of the minimum stretch spanning tree problem
- Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
- ON SPANNERS OF GEOMETRIC GRAPHS
- Tree spanners on chordal graphs: complexity and algorithms
- Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
- Spanners of bounded degree graphs
- Isomorphic tree spanner problems
- Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
- Minimum spanners of butterfly graphs
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Hardness and efficiency on minimizing maximum distances in spanning trees
- Approximating \(k\)-spanner problems for \(k>2\)
- Spanners for bounded tree-length graphs
- Approximation of minimum weight spanners for sparse graphs
- Edge-disjoint spanners of complete graphs and complete digraphs
- An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
- Edge tree spanners
- Minimax flow tree problems
- Swapping labeled tokens on graphs
- Computing geometric minimum-dilation graphs is NP-hard
- A distance approximating trees
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
- Additive sparse spanners for graphs with bounded length of largest induced cycle
- Title not available (Why is that?)
- Spanners and message distribution in networks.
- Title not available (Why is that?)
- A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph
- A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
- Spanning trees with disjoint dominating and 2-dominating sets
- Tree-decompositions with bags of small diameter
- Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction.
- The minimum centroid branch spanning tree problem
- On central spanning trees of a graph
- Tree 3-spanners on generalized prisms of graphs
- Hardness and efficiency on \(t\)-admissibility for graph operations
- Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \)
- Graphs with minimum spanner \(\varsigma(G)\geq2\rho-1\)
- Network flow spanners
- Well-partitioned chordal graphs
- Max-stretch reduction for tree spanners
- Better hardness results for the minimum spanning tree congestion problem
- Semi‐labeled unrooted binary tree optimization subject to nonnegativity
- Complexity of the multiobjective minimum weight minimum stretch spanner problem
- Minimum \(t\)-spanners on subcubic graphs
- Polynomial algorithms for sparse spanners on subcubic graphs
- Title not available (Why is that?)
- Three problems on well-partitioned chordal graphs
- Independent tree spanners: Fault-tolerant spanning trees with constant distance guarantees
- Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes
- Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
- A Survey on Spanning Tree Congestion
- New results on edge-coloring and total-coloring of split graphs
- Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
- Collective Additive Tree Spanners of Homogeneously Orderable Graphs
- Better hardness results for the minimum spanning tree congestion problem
- Additive tree 2-spanners of permutation graphs
- Distance domination and amplifier placement problems
- Algorithms and Data Structures
- Sorting on graphs by adjacent swaps using permutation groups
- Bounds on the Spanner-Sum of Torus
This page was built for publication: Tree Spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4847362)
