Diameter-Constrained Minimum Spanning Tree Problems: A Survey

The diameter of a tree is a measure of the longest path between any two nodes in the tree where this path is defined in terms of the number of edges. A Diameter-Constrained Minimum Spanning Tree (DCMST) is a minimum-weight spanning tree with a diameter less than a given integer. Finding a DCMST is an NP-complete problem, and it may require searching through all possible spanning trees with acceptable diameters and finding the minimum. There have been a number of algorithms proposed for finding a DCMST efficiently. These algorithms can be broadly classified into two categories: exact algorithms and approximate algorithms. Exact algorithms are able to find the exact DCMST but generally have a higher time complexity and they are not suitable for very large trees. Approximate algorithms, on the other hand, are able to find an approximate DCMST, but may not be as accurate as the exact algorithms. In this survey, we review various algorithms that have been proposed for solving the DCMST problem and compare their performance in terms of time complexity, accuracy, and other relevant factors. Over-all, the problem of finding the DCMST is an active area of research, and there is still room for further improvement in the efficiency and accuracy of the existing algorithms.