The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph
Pages 341 - 348
Abstract
We consider the following NP-hard problem. Given an undirected complete edge-weighted graph and positive integers m, D, the goal is to find m edge-disjoint spanning trees with diameter D of maximum total weight in complete undirected graph. We propose an -time approximation algorithm for the problem, where n is the number of vertices in the input graph. For the case when edge weights are randomly uniformly chosen from the interval (0; 1), we prove sufficient conditions under which the proposed algorithm gives asymptotically optimal solutions.
References
[1]
Angel O, Flaxman AD, and Wilson DB A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks Combinatorica 2012 32 1 1-33
[2]
Bala, K., Petropoulos, K., Stern, T.E.: Multicasting in a linear Lightwave network. In: Proceedings of the IEEE INFOCOM 1993, pp. 1350–1358 (1993).
[3]
Bookstein A and Klein ST Compression of correlated bit-vectors Inform. Syst. 1991 16 4 387-400
[4]
Clementi, A.E.F., Ianni, M.D., Monti, A., Rossi, G., Silvestri, R.: Experimental analysis of practically efficient algorithms for bounded-hop accumulation in ad-hoc wireless networks. In: Proceedings of the 19th IEEE International Parallel Distributed Processing Symposium (IPDPS 2005), pp. 8–16 (2005).
[5]
Cooper C, Frieze A, Ince N, Janson S, and Spencer J On the length of a random minimum spanning tree Comb. Probab. Comput. 2016 25 1 89-107
[6]
Erzin AI The problem of constructing a spanning tree of maximal weight with a bounded radius Upravlyaemye Sistemy, iss. 1987 27 70-78 (in Russian)
[7]
Frieze A On the value of a random MST problem Discret. Appl. Math. 1985 10 1 47-56
[8]
Garey, M.R., Johnson, D.S.: Computers and Intractability, p. 340. Freeman, San Francisco (1979)
[9]
Gimadi EK, Glebov NI, and Perepelitsa VA Algorithms with estimates for discrete optimization problems Problemy Kibernetiki, iss. 1975 31 35-42 (in Russian)
[10]
Gimadi, E. K., Istomin, A.M., Shin, E.Y.: On algorithm for the minimum spanning tree problem bounded below. In: Proceedings of the DOOR 2016, Vladivostok, Russia, 19–23 September 2016, CEUR-WS, 1623, pp. 11–17 (2016)
[11]
Gimadi, E.K., Istomin, A.M., Shin, E.Y.: On given diameter MST problem on random instances. In: CEUR Workshop Proceedings, pp. 159–168 (2019)
[12]
Gimadi EK and Serdyukov AI Inderfurth K, Schwödiauer G, Domschke W, Juhnke F, Kleinschmidt P, and Wäscher G A probabilistic analysis of an approximation algorithm for the minimum weight spanning tree problem with bounded from below diameter Operations Research Proceedings 1999 2000 Heidelberg Springer 63-68
[13]
Gimadi, E.K., Shevyakov, A.S., Shin, E.Y.: Asymptotically optimal approach to a given diameter undirected MST problem on random instances. In: Proceedings of 15-th International Asian School-Seminar OPCS-2019, Publisher: IEEE Xplore, pp. 48–52 (2019)
[14]
Gimadi EK and Shtepa AA Asymptotically optimal approach for the maximum spanning tree problem with given diameter in a complete undirected graph on UNI(0; 1)-entries Problems Inform. 2022 57 4 53-62
[15]
Gimadi, E.K., 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, 84(7), 872–888 (2023).
[16]
Nadiradze, G.: Bounded Diameter Minimum Spanning Tree, Master thesis, Central European University (2013)
[17]
Petrov, V.V.: Limit Theorems of Probability Theory. Sequences of Independent Random Variables, p. 304. Clarendon Press, Oxford (1995)
[18]
Raymond K A tree-based algorithm for distributed mutual exclusion ACM Trans. Comput. Syst. 1989 7 1 61-77
[19]
Serdyukov, A.I.: On problem of maximal spanning tree with bounded radius. Diskretn. Anal. Issled. Oper. Ser. 1, 5(3), 64–69 (1998). (in Russian)
Recommendations
On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter
AbstractWe consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several ...
On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights
Mathematical Optimization Theory and Operations ResearchAbstractWe consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter in an graph with random edge weights. Earlier, we have implemented an asymptotically optimal approach for this problem in the case of directed ...
Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph
An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2023
375 pages
ISBN:978-3-031-54533-7
DOI:10.1007/978-3-031-54534-4
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 12 March 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in