On the complexity of the cable-trench problem

DOI10.1016/j.dam.2023.07.010OpenAlexW4385523147MaRDI QIDQ6048437

Marcelo P. L. Benedito, Hugo K. K. Rosado, Lehilton L. C. Pedrosa

Publication date: 14 September 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2023.07.010

zbMATH Keywords

approximationSteiner treehardnessinapproximabilityparameterized algorithmcable-trench

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The Steiner tree problem on graphs: inapproximability results
• A Benders decomposition based framework for solving cable trench problems
• Balancing minimum spanning trees and shortest-path trees
• Modeling the capacitated \(p\)-cable trench problem with facility costs
• An improved approximation algorithm for the uniform cost-distance Steiner tree problem
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
• The Design of Approximation Algorithms
• Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
• On the power of unique 2-prover 1-round games
• Tighter Bounds for Graph Steiner Tree Approximation
• Formulating and solving a radio astronomy antenna connection problem as a generalized cable‐trench problem: an empirical study
• Steiner Tree Approximation via Iterative Randomized Rounding
• Parameterized Algorithms
• The steiner problem in graphs
• Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
• The cable trench problem: Combining the shortest path and minimum spanning tree problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of the cable-trench problem