A simple and efficient strategy for solving very large-scale generalized cable-trench problems

Vasko et al. (2002), defined the cable-trench problem (CTP) as a combination of the Shortest Path and Minimum Spanning Tree Problems. Specifically, let G = ( V , E ) be a connected weighted graph with specified vertex v 1 ∈ V (referred to as the root), length l ( e ) ≥ 0 for each e ∈ E , and positive parameters τ and γ . The CTP is the problem of finding a spanning tree T of G such that τ l τ ( T ) + γ l γ ( T ) is minimized, where l τ ( T ) is the total length of the spanning tree T and l γ ( T ) is the total path length in T from v 1 to all other vertices of V . Recently, Jiang et al. (2011), modeled the vascular network connectivity problem in medical image analysis as an extraordinarily large-scale application of the generalized cable-trench problem (GCTP). They proposed an efficient solution based on a modification of Prim's algorithm (MOD_PRIM), but did not elaborate on it. In this article, we formally define the GCTP, describe MOD_PRIM in detail, and describe two linearly parallelizable metaheuristics which significantly improve the performance of MOD_PRIM. These metaheuristics are capable of finding near-optimal solutions of very large GCTPs in quadratic time in | V | . We also give empirical results for graphs with up to 25,001 vertices.