Anzeige
Erschienen in:
05.05.2020
Exact algorithms for finding constrained minimum spanning trees
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2022
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
For a given undirected graph with each edge associated with a weight and a length, the constrained minimum spanning tree (CMST) problem aims to compute a minimum weight spanning tree with total length bounded by a given fixed integer \(L\in {\mathbb {Z}}^{+}\). In the paper, we first present an exact algorithm with a runtime \(O(mn^{2})\) for CMST when the edge length is restricted to 0 and 1 based on combining the local search method and our developed bicameral edge replacement approach. Then we extend the algorithm to solve a more general case when the edge length is restricted to 0, 1 and 2 via iteratively improving a feasible solution of CMST towards an optimum solution. At last, numerical experiments are carried out to validate the practical performance of the proposed algorithms by comparing with previous algorithms as baselines.