The cable trench problem: combining the shortest path and minimum spanning tree problems

Let G = (V, E) be a connected graph with specified vertex upsilon (0) is an element of V, length l(e) greater than or equal to 0 for each e is an element of E, and positive parameters tau and gamma. The cable-trench problem (CTP) is to find a spanning tree T such that taul(tau)(T) + gammal(gamma)(T) is minimized where l(tau)(T) is the total length of the spanning tree T and l(gamma)(T) is the total path length in T from upsilon (0) to all other vertices of V. Since all vertices must be connected to upsilon (0) and only edges from E are allowed, the solution will not be a Steiner tree. Consider the ratio R = tau/gamma. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. In this paper, the CTP will be shown to be NP-complete. A mathematical formulation for the CTP will be provided for specific values of tau and gamma. Also, a heuristic will be discussed that will solve the CTP for all values of R.