EDGE-DISJOINT SPANNING TREES OF ARBITRARY BOUNDED DIAMETER ON RANDOM INPUTS

Edward Kh. Gimadi     (Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, 4 pr. Akad. Koptyug, Novosibirsk, 630090, Russian Federation)
Oxana Yu. Tsidulko     (Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, 4 pr. Akad. Koptyug, Novosibirsk, 630090, Russian Federation)

Abstract


We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected \(n\)-vertex edge-weighted complete graph and integers \(d\) and \(m\), find \(m\) edge-disjoint spanning trees of diameter at most \(d\) with minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge weights of the graph are i. i. d. random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal for the case of continuous and discrete uniform distribution on \([a_n, b_n]\), \(a_n>0\), the shifted exponential distribution with shift \(a_n>0\), and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if \(d\) tends to infinity with \(n\), but for constant \(d\) as well.


Keywords


Edge-disjoint spanning trees, Bounded diameter, Random inputs, Asymptotically optimal algorithm, Probabilistic analysis

Full Text:

PDF

References


  1. Anderson R., Stenger B., Cipolla R. Using bounded diameter minimum spanning trees to build dense active appearance models. Int. J. Comput. Vis., 2014. Vol. 110. P. 48–57. DOI: 10.1007/s11263-013-0661-9
  2.  Angel O., Flaxman A.D., Wilson D.B. A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks. Combinatorica, 2012. Vol. 32, P. 1–33. DOI: 10.1007/s00493-012-2552-z
  3. Bala K., Petropoulos K., Stern T.E. Multicasting in a linear lightwave network. In: Proc. IEEE INFOCOM’93 The Conf. on Computer Communications, San Francisco. CA, USA, 1993. Vol. 3. P. 1350–1358. DOI: 10.1109/INFCOM.1993.253399
  4. Bar-Ilan J., Kortsarz G., Peleg D. Generalized submodular cover problems and applications. Theoret. Comput. Sci., 2001. Vol. 250, No. 1–2. P. 179–200. DOI: 10.1016/S0304-3975(99)00130-9
  5. Boruvka O. O jistém problému minimálním. Prace Mor. Prirodoved. Spol. V Brne III, 1926. Vol. 3, P. 37–58. (in Czech)
  6. Frieze A. On the value of a random minimum spanning tree problem. Discrete Appl. Math., 1985. Vol. 10, No. 1. P. 47–56. DOI: 10.1016/0166-218X(85)90058-7
  7. Garey M.R., Johnson D.S. Computers and Intractability; A Guide to the Theory of NP-Completeness. USA: W.H. Freeman & Co.: 1990. 338 p.
  8. Gimadi E.Kh. On some probability inequalities for some discrete optimization problems. Oper. Res. Proc., vol. 2005. HD. Haasis, H. Kopfer, J. Schonberger (eds.). Berlin, Heidelberg: Springer, 2006. P. 283–289. DOI: 10.1007/3-540-32539-5_45
  9. Gimadi E.Kh. Several edge-disjoint spanning trees with given diameter in a graph with random discrete edge weights. In: Commun. Comput. Inf. Sci., vol. 1913: Advances in Optimization and Applications (OPTIMA 2023), N. Olenev et al. (eds.). Cham: Springer, 2024. P. 281–292. DOI: 10.1007/978-3-031-48751-4_21
  10. Gimadi E.Kh., Istomin A.M., Shin E.Yu. On algorithm for the minimum spanning tree problem bounded below. In: CEUR Workshop Proc., vol. 1623: Suppl. Proc. 9th Int. Conf. on Discrete Optimization and Operations Research and Scientific School (DOOR 2016), Vladivostok, Russia, September 19–23, 2016. CEUR-WS, 2016. P. 11–17. URL: https://ceur-ws.org/Vol-1623/paperco4.pdf
  11. Gimadi E.Kh., Istomin A.M., Shin E.Yu. On bounded diameter MST problem on random instances. In: CEUR Workshop Proc., vol. 2098: Proc. School-Seminar on Optimization Problems and their Applications (OPTA-SCL 2018), Omsk, Russia, July 8-14, 2018. CEUR WP, 2018. P. 159–168. URL: https://ceur-ws.org/Vol-2098/paper14.pdf
  12. Gimadi E.Kh., Shevyakov A.S., Shtepa A.A. A given diameter MST on a random graph. In: Lecture Notes in Comput. Sci., vol. 12422: Optimization and Applications (OPTIMA 2020), N. Olenev et al. (eds.). Cham: Springer, 2020. P. 110–121. DOI: 10.1007/978-3-030-62867-3_9
  13. Gimadi E.Kh., Shin E.Yu. Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below. J. Appl. Ind. Math., 2015. Vol. 9, No. 4. P. 480–488. DOI: 10.1134/S1990478915040043
  14. Gimadi E.Kh., Shtepa A.A. On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter. Autom. Remote Control, 2023. Vol. 84. P. 772–787. DOI: 10.1134/S0005117923070068
  15. Gimadi E.K., Tsidulko O.Y. An asymptotically optimal algorithm for the minimum weight spanning tree with arbitrarily bounded diameter on random inputs. In: Lecture Notes in Comput. Sci., vol. 15419: Analysis of Images, Social Networks and Texts (AIST 2024), A. Panchenko et al. (eds.). Cham: Springer, 2025. P. 249–261. DOI: 10.1007/978-3-031-88036-0_15
  16.  Gimadi E.K., Istomin A.M., Tsidulko O.Y. On asymptotically optimal approach to the \(m\)-peripatetic salesman problem on random inputs. In: Lecture Notes in Comput. Sci., vol. 9869: Discrete Optimization and Operations Research (DOOR 2016), Y. Kochetov et al. (eds.). Cham: Springer, 2016. P. 136–147. DOI: 10.1007/978-3-319-44914-2_11
  17. Gimadi E.K., Le Gallou A., Shakhshneyder A.V. Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded above instances. J. Appl. Ind. Math., 2009. Vol. 3. P. 207–221. DOI:  10.1134/S1990478909020070
  18. Gimadi E.Kh., Glazkov Yu.V. An asymptotically exact algorithm for one modification of planar three-index assignment problem. J. Appl. Indust. Math., 2007. Vol. 1, No. 4. P. 442–452. DOI: 10.1134/S1990478907040072
  19. Gouveia L., Magnanti T.L. Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks, 2003. Vol. 41, No. 3. P. 159–173. DOI: 10.1002/net.10069
  20. Gruber M. Exact and Heuristic Approaches for Solving the Bounded Diameter Minimum Spanning Tree Problem. PhD Thesis. Vienna University of Technology, 2008. 156 p.
  21. Kruskal J.B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 1956. Vol. 7, No. 1. P. 48–50. DOI: 10.1090/S0002-9939-1956-0078686-7
  22. Lemke P. The Bounded Diameter Two Edge-Disjoint Spanning Trees Problem is NP-Complete. Inst. Math. Appl., IMA Preprints Series, 1988. https://hdl.handle.net/11299/4860
  23. Petrov V.V. Limit Theorems of Probability Theory. Sequences of Independent Random Variables. Oxford: Clarendon Press, 1995. 304 p. DOI: 10.1093/oso/9780198534990.001.0001
  24. Prim R.C. Shortest connection networks and some generalizations. Bell Syst. Tech. J., 1957. Vol. 36, No. 6. P. 1389–1401. DOI: 10.1002/j.1538-7305.1957.tb01515.x
  25. Roskind J., Tarjan R.E. A note on finding minimum-cost edge-disjoint spanning trees. Math. Oper. Res., 1985. Vol. 10, No. 4. P. 701–708. DOI: 10.1287/moor.10.4.701
  26. Segal M., Tzfaty O. Finding bounded diameter minimum spanning tree in general graphs. Comput. Oper. Res., 2022. Vol. 144. Art. no. 105822. DOI: 10.1016/j.cor.2022.105822
  27. Torkestani J.A. A stable virtual backbone for wireless MANETS. Telecommun. Syst., 2014. Vol. 55. No. 1. P. 137–148. DOI: 10.1007/s11235-013-9760-8




DOI: http://dx.doi.org/10.15826/umj.2025.2.007

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.