Finding bounded diameter minimum spanning tree in general graphs. (August 2022)

• Record Type: Journal Article
• Authors: Segal, Michael; Tzfaty, Oren
• Is Part Of: Computers & operations research. Volume 144(2022)
• Publication Date: 2022-08
• Subjects: Graph theory -- Minimum spanning tree -- Bounded diameter minimum spanning tree; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105822
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Given a connected, weighted, undirected graph G = ( V, E ) and a constant D ≥ 2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight with diameter no more than D . A new algorithm addresses graphs with non-negative weights and has proven performance ratio of O 1 − D d m i n ( | V | − 1 ) w + / w − + 1, where w + (resp. w − ) denotes the maximum (resp. minimum) edge weight in the graph, and d m i n is the hop diameter of G . The running time of the algorithm is O | V | log D after minimum spanning tree of G is computed. The performance of the algorithm has been evaluated empirically as well. Highlights: Novel algorithm for finding a bounded diameter MST in general graphs is presented. The performance is bounded by the ratio depending on the weights of the heaviest and lightest edges in the tree. The algorithm is based on continuous growing the tree in each one of the nodes.