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

Vasko et al., Comput Oper Res 29 (2002), 441–458 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 vertexv 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, wherel τ ( T )is the total length of the spanning tree T andl γ ( T ) is the total path length in T fromv 1to all other vertices of V . Recently, Jiang et al., Proceedings of MICCAI 6893 (2011), 528–536 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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 199–208 2016