Tree Spanners
From MaRDI portal
Publication:4847362
DOI10.1137/S0895480192237403zbMath0832.05037OpenAlexW2912257407WikidataQ30052585 ScholiaQ30052585MaRDI QIDQ4847362
Leizhen Cai, Derek Gordon 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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (73)
On approximating tree spanners that are breadth first search trees ⋮ Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ A Survey on Spanning Tree Congestion ⋮ Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs ⋮ Tree spanners on chordal graphs: complexity and algorithms ⋮ Tree-decompositions with bags of small diameter ⋮ Distance approximating spanning trees ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ Well-partitioned chordal graphs ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ Spanners for bounded tree-length graphs ⋮ A Faster Computation of All the Best Swap Edges of a Tree Spanner ⋮ Isomorphic tree spanner problems ⋮ On spanning 2-trees in a graph ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Bounds on the Spanner-Sum of Torus ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard ⋮ General variable neighborhood search for the minimum stretch spanning tree problem ⋮ Semi‐labeled unrooted binary tree optimization subject to nonnegativity ⋮ Better hardness results for the minimum spanning tree congestion problem ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Tree spanners of bounded degree graphs ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Hardness and efficiency on minimizing maximum distances in spanning trees ⋮ Spanners of bounded degree graphs ⋮ Three problems on well-partitioned chordal graphs ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ Spanners and message distribution in networks. ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Spanners in sparse graphs ⋮ A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ A distance approximating trees ⋮ An improved algorithm for computing all the best swap edges of a tree spanner ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ The zoo of tree spanner problems ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Tree spanners in planar graphs ⋮ Independent tree spanners: Fault-tolerant spanning trees with constant distance guarantees ⋮ Max-stretch reduction for tree spanners ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Spanning tree congestion of \(k\)-outerplanar graphs ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Graph spanners: a tutorial review ⋮ Minimax flow tree problems ⋮ Network flow spanners ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ Collective Additive Tree Spanners of Homogeneously Orderable Graphs ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ The minimum stretch spanning tree problem for typical 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 ⋮ Edge tree spanners ⋮ Spanning trees with disjoint dominating and 2-dominating sets ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Additive tree 2-spanners of permutation graphs ⋮ The non-approximability of bicriteria network design problems ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem ⋮ Edge-disjoint spanners of complete graphs and complete digraphs ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle ⋮ Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction. ⋮ Swapping labeled tokens on graphs ⋮ An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner ⋮ NP-completeness of minimum spanner problems ⋮ Low complexity variants of the arrow distributed directory
This page was built for publication: Tree Spanners
