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

DOI10.1016/S0305-0548(00)00083-6zbMath0994.90124MaRDI QIDQ5959396

Kenneth L. jun. Stott, Francis J. Vasko, Robert S. Barbieri, Kenneth L. Reitmeyer, Brian Q. Rieksts

Publication date: 10 October 2002

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

spanning treeNP-completecable-trench problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (8)

The \(p\)-arborescence star problem: formulations and exact solution approaches ⋮ An improved algorithm for solving biobjective integer programs ⋮ A Benders decomposition based framework for solving cable trench problems ⋮ Cost optimized design for the local wind turbine grid of an onshore wind farm ⋮ On the complexity of the cable-trench problem ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ Lagrangean relaxation heuristics for the \(p\)-cable-trench problem ⋮ Modeling the capacitated \(p\)-cable trench problem with facility costs

Cites Work

• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• A constrained minimum spanning tree problem
• Genetic algorithm approach on multi-criteria minimum spanning tree problem
• Balancing minimum spanning trees and shortest-path trees
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The cable trench problem: Combining the shortest path and minimum spanning tree problems