The minimum stretch spanning tree problem for typical graphs
From MaRDI portal
Abstract: With applications in distribution systems and communication networks, the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized. The problem has been proved to be NP-hard and fixed-parameter polynomial algorithms have been obtained for some special classes of graphs. In this paper, we concentrate on the optimality characterizations for typical classes of graphs. We determine the exact optimality representations for Petersen graph, the complete k-partite graphs, split graphs, generalized convex graphs, and several planar grids, including rectangular grids, triangular grids, and triangular-rectangular grids.
Recommendations
- Optimality computation of the minimum stretch spanning tree problem
- Optimality characterization of the minimum stretch spanning tree problem for interval graphs
- On minimum average stretch spanning trees in grid graphs
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Optimization of spanning tree stretch and congestion for graphs
Cites work
- An Optimal Synchronizer for the Hypercube
- Cutwidth of triangular grids
- Graph theory
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 4070955 (Why is no real title available?)
- Minimal congestion trees
- Minimum congestion spanning trees in planar graphs
- Minimum congestion spanning trees of grids and discrete toruses
- On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
- On spanning tree congestion of graphs
- On tree congestion of graphs
- Parameterized complexity of the spanning tree congestion problem
- Restrictions of minimum spanner problems
- Spanners of bounded degree graphs
- Spanning tree congestion of k-outerplanar graphs
- The zoo of tree spanner problems
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- 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
(12)- On minimum average stretch spanning trees in polygonal 2-trees
- Optimality computation of the minimum stretch spanning tree problem
- THE MINIMUM SPANNING TREE PROBLEM: Jarník's solution in historical and present context
- Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
- Optimality characterization of the minimum stretch spanning tree problem for interval graphs
- Optimization of spanning tree stretch and congestion for graphs
- On minimum average stretch spanning trees in grid graphs
- Distance domination and amplifier placement problems
- On minimum average stretch spanning trees in polygonal 2-trees
- General variable neighborhood search for the minimum stretch spanning tree problem
- The minimum centroid branch spanning tree problem
- Carousel greedy algorithms for the minimum stretch spanning tree problem
This page was built for publication: The minimum stretch spanning tree problem for typical graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2046233)
