The minimum stretch spanning tree problem for typical graphs. (English) Zbl 1473.90141
Summary: With applications in 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 NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs. In this paper, we concentrate on the optimality characterizations for typical classes of graphs. We determine the exact formulae for the complete \(k\)-partite graphs, split graphs, generalized convex graphs, and several planar grids, including rectangular grids, triangular grids, and triangulated-rectangular grids.
References:
| [1] | Bondy, JA; Murty, USR, Graph Theory (2008), Berlin: Springer-Verlag, Berlin · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5 |
| [2] | Bodlaender, HL; Kozawa, K.; Matsushima, T.; Otachi, Y., Spanning tree congestion of k-outerplanar graphs, Discrete Mathematics, 311, 1040-1045 (2011) · Zbl 1223.05017 · doi:10.1016/j.disc.2011.03.002 |
| [3] | Bodlaender, HL; Fomin, FV; Golovach, PA; Otachi, Y.; van Leeuwen, EJ, Parameterized complexity of the spanning tree congestion problem, Algorithmica, 64, 85-111 (2012) · Zbl 1253.68163 · doi:10.1007/s00453-011-9565-7 |
| [4] | Brandstädt, A.; Dragan, FF; Le, H-O; Le, VB, Tree spanners on chordal graphs: complexity and algorithms, Theoretical Computer Science, 310, 329-354 (2004) · Zbl 1049.05075 · doi:10.1016/S0304-3975(03)00424-9 |
| [5] | Brandstaädt, A.; Dragan, FF; Le, H-O; Le, VB; Uehara, R., Tree spanners for bipartite graphs and probe interval graphs, Algorithmica, 47, 27-51 (2007) · Zbl 1107.68062 · doi:10.1007/s00453-006-1209-y |
| [6] | Cai, L.; Corneil, DG, Tree spanners, SIAM Journal of Discrete Mathematics, 8, 359-387 (1995) · Zbl 0832.05037 · doi:10.1137/S0895480192237403 |
| [7] | Castejón, A.; Ostrovskii, MI, Minimum congestion spanning trees of grids and discrete toruses, Discussiones Mathematicae Graph Theory, 29, 511-519 (2009) · Zbl 1193.05058 · doi:10.7151/dmgt.1461 |
| [8] | Chung, F.R.K. Labelings of graphs. In: Beineke, L.W., Wilson, R.J. (eds.), Selected Topics in Graph Theory, 3: 151-168, 1988 · Zbl 0656.05058 |
| [9] | Diaz, J.; Petit, J.; Serna, M., A survey of graph layout problems, ACM Computing Surveys, 34, 313-356 (2002) · doi:10.1145/568522.568523 |
| [10] | Fekete, SP; Kremer, J., Tree spanners in planar graphs, Discrete Applied Mathematics, 108, 85-103 (2001) · Zbl 0969.68111 · doi:10.1016/S0166-218X(00)00226-2 |
| [11] | Fomin, FV; Golovach, PA; van Leeuwen, EJ, Spanners on bounded degree graphs, Information Processing Letters, 111, 142-144 (2011) · Zbl 1260.68154 · doi:10.1016/j.ipl.2010.10.021 |
| [12] | Galbiati, G., On finding cycle bases and fundamental cycle bases with a shortest maximal cycles, Information Processing Letters, 88, 155-159 (2003) · Zbl 1178.68679 · doi:10.1016/j.ipl.2003.07.003 |
| [13] | Golumbic, MC, Algorithmic Graph Theory and Perfect graphs (1980), New York: Academic Press, New York · Zbl 0541.05054 |
| [14] | Hruska, SW, On tree congestion of graphs, Discrete Mathematics, 308, 1801-1809 (2008) · Zbl 1151.05014 · doi:10.1016/j.disc.2007.04.030 |
| [15] | Kozawa, K.; Otachi, Y.; Yamazaki, K., On spanning tree congestion of graphs, Discrete Mathematics, 309, 4215-4224 (2009) · Zbl 1232.05116 · doi:10.1016/j.disc.2008.12.021 |
| [16] | Liebchen, C.; Wünsch, G., The zoo of tree spanner problems, Discrete Applied Mathematics, 156, 569-587 (2008) · Zbl 1176.90504 · doi:10.1016/j.dam.2007.07.001 |
| [17] | Lin, L.; Lin, Y.; West, D., Cutwidth of triangular grids, Discrete Mathematics, 331, 89-92 (2014) · Zbl 1297.05206 · doi:10.1016/j.disc.2014.04.029 |
| [18] | Madanlal, MS; Venkatesan, G.; Rangan, PC, Tree 3-spanners on interval, permutation and regular bipartite graphs, Information Processing Letters, 59, 97-102 (1996) · Zbl 0900.68332 · doi:10.1016/0020-0190(96)00078-6 |
| [19] | Okamoto, Y.; Otachi, Y.; Uehara, R.; Uno, T., Hardness results and an exact exponential algorithm for the spanning tree congestion problem, Journal of Graph Algorithms and Applications, 15, 6, 727-751 (2011) · Zbl 1276.05030 · doi:10.7155/jgaa.00246 |
| [20] | Ostrovskii, MI, Minimal congestion trees, Discrete Mathematics, 285, 219-326 (2004) · Zbl 1051.05032 · doi:10.1016/j.disc.2004.02.009 |
| [21] | Ostrovskii, MI, Minimum congestion spanning trees in planar graphs, Discrete Mathematics, 310, 1204-1209 (2010) · Zbl 1230.05112 · doi:10.1016/j.disc.2009.11.016 |
| [22] | Peleg, D.; Ullman, JJ, An optimal synchroniser for the hypercube, SIAM Journal of Computing, 18, 4, 740-747 (1989) · Zbl 0681.68091 · doi:10.1137/0218050 |
| [23] | Venkatesan, G.; Rotics, U.; Madanlal, MS; Makowsy, JA; Rangan, CP, Restrictions of minimum spanner problems, Information and Computation, 136, 143-164 (1997) · Zbl 0890.68106 · doi:10.1006/inco.1997.2641 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
