Abstract
Motivated by applications in communication networks of the diameter-constrained minimum spanning tree problem, we consider the delay-constrained minimum shortest path tree (DcMSPT) problem. Specifically, given a weighted graph \(G=(V,E;w,c)\) and a constant \(d_0\), where length function \(w: E \rightarrow R^+\) and cost function \(c: E \rightarrow R^+\), we are asked to find a minimum cost shortest path tree among all shortest path trees (in G) whose delays are no more than \(d_0\), where the delay of a shortest path tree is the maximum distance (depending on \(w(\cdot )\)) from its source to every other leaves in that tree, and the cost of a shortest path tree is the sum of costs of all edges (depending on \(c(\cdot )\)) in that tree. Particularly, when a constant \(d_0\) is exactly the radius of G, we refer to this version of the DcMSPT problem as the minimum radius minimum shortest path tree (MRMSPT) problem. Similarly, the maximum delay minimum shortest path tree (MDMSPT) problem is asked to find a minimum cost shortest path tree among all shortest path trees (in G) whose delays are exactly the diameter of G.
We obtain the following two main results. (1) We design an exact algorithm in time \(O(n^3)\) to solve the DcMSPT problem, and we provide the similar algorithm to solve the MRMSPT problem; (2) We present an exact algorithm in time \(O(n^3)\) to solve the MDMSPT problem.
This paper is supported by the National Natural Science Foundation of China [Nos. 11861075, 12101593], Project for Innovation Team (Cultivation) of Yunnan Province [No. 202005AE160006], Key Project of Yunnan Provincial Science and Technology Department and Yunnan University [No. 2018FY001014] and Program for Innovative Research Team (in Science and Technology) in Universities of Yunnan Province [C176240111009]. Jianping Li is also supported by Project of Yunling Scholars Training of Yunnan Province.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R.: Graph theory. In: Graduate Texts in Mathematics, vol. 244. Springer, Heidelberg (2008)
Bookstein, A., Klein, S.T.: Construction of optimal graphs for bit-vector compression. In: Proceedings of the 13th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 327–342 (1990)
Bookstein, A., Klein, S.T.: Compression of correlated bit-vectors. Inf. Syst. 16, 387–400 (1991)
Cheriton, D., Tarjan, R.: Finding minimum spanning trees. SIAM J. Comput. 5, 724–742 (1976)
Chu, Y.J., Liu, Z.H.: On the shortest arborescence of a directed graph. Scientia Sinica 14, 1396–1400 (1965)
Dantzig, G.B.: Discrete-variable extremum problems. Oper. Res. 5, 266–277 (1957)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Dvir, D., Handler, G.Y.: The absolute center of a network. Networks 43(2), 109–118 (2004)
Edmonds, J.: Optimum branchings. J. Res. Natl. Bureau Stand. Sect. B 71, 233–240 (1967)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Hakimi, S.L.: Optimal locations of switching centers and medians of a graph. Oper. Res. 12, 450–459 (1964)
Hassin, R., Tamir, A.: On the minimum diameter spanning tree problem. Inf. Process. Lett. 53, 109–111 (1995)
Ho, J.M., Lee, D.T., Chang, C.H., Wong, C.K.: Minimum diameter spanning trees and related problems. SIAM J. Comput. 20(5), 987–997 (1991)
Julstrom, B.A.: Greedy heuristics for the bounded diameter minimum spanning tree problem, ACM J. Exp. Algorithmics 14, Article No. 1.1 (2009)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Berlin (2012)
Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Appl. Math. 93, 265–285 (1999)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, The Netherlands (2003)
Seo, D.Y., Lee, D.T., Lin, T.-C.: Geometric minimum diameter minimum cost spanning tree problem. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 283–292. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10631-6_30
Singh, A., Gupta, A.K.: Improved heuristics for the bounded-diameter minimum spanning tree problem. Soft Comput. 11, 911–921 (2007)
Torkestani, J.A.: An adaptive heuristic to the bounded-diameter minimum spanning tree problem. Soft Comput. 16, 1977–1988 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Lichen, J., Cai, L., Li, J., Liu, S., Pan, P., Wang, W. (2021). Delay-Constrained Minimum Shortest Path Trees and Related Problems. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_53
Download citation
DOI: https://doi.org/10.1007/978-3-030-92681-6_53
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92680-9
Online ISBN: 978-3-030-92681-6
eBook Packages: Computer ScienceComputer Science (R0)