Indexed by:
Abstract:
Given an integer L is an element of Z(+) and an undirected graph with a weight and a length associated with every edge, the constrained minimum spanning tree (CMST) problem is to compute a minimum weight spanning tree with total length bounded by L. The problem was shown weakly NP-hard in [1], admitting a PTAS with a runtime O(n(O(1/epsilon))(m log(2) n + n log(3) n)) due to Ravi and Goemans [13]. In the paper, we present an exact algorithm for CMST, based on our developed bicameral edge replacement which improves a feasible solution of CMST towards an optimal solution. By applying the classical rounding and scaling technique to the exact algorithm, we can obtain a fully polynomial-time approximation scheme (FPTAS), i.e. an approximation algorithm with a ratio (1 + epsilon) and a runtime O(mn(5) 1/c(2)), where epsilon > 0 is any fixed real number.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I
ISSN: 0302-9743
Year: 2017
Volume: 10627
Page: 103-110
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: