Exact algorithms for finding constrained minimum spanning trees

Pei Yao () and Longkun Guo ()
Additional contact information
Pei Yao: Fuzhou University
Longkun Guo: Fuzhou University

Journal of Combinatorial Optimization, No 0, 19 pages

Abstract: 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}}^{+}$$L∈Z+. In the paper, we first present an exact algorithm with a runtime $$O(mn^{2})$$O(mn2) 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.

Keywords: Constrained minimum spanning tree; Bicameral edge replacement; Local search (search for similar items in EconPapers)
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00579-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00579-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00579-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().