On the complexity of the cable-trench problem

DOI10.1016/J.DAM.2023.07.010MaRDI QIDQ6048437zbMATH OpenOpenAlexFDO

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

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

approximationcable-trenchhardnessinapproximabilityparameterized algorithmSteiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• The cable trench problem: Combining the shortest path and minimum spanning tree problems
• The generalized Steiner cable-trench problem with application to error correction in vascular image analysis
• Automata, Languages and Programming
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• The Steiner tree problem on graphs: inapproximability results

Cites work

• A Benders decomposition based framework for solving cable trench problems
• A deterministic algorithm for the cost-distance problem
• A note on two problems in connexion with graphs
• An improved approximation algorithm for the uniform cost-distance Steiner tree problem
• Balancing minimum spanning trees and shortest-path trees
• Formulating and solving a radio astronomy antenna connection problem as a generalized cable-trench problem: an empirical study
• scientific article; zbMATH DE number 2011853 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Modeling the capacitated \(p\)-cable trench problem with facility costs
• On the power of unique 2-prover 1-round games
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Parameterized algorithms
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Steiner tree approximation via iterative randomized rounding
• Subexponential-time parameterized algorithm for Steiner tree on planar graphs
• The cable trench problem: Combining the shortest path and minimum spanning tree problems
• The design of approximation algorithms
• The steiner problem in graphs
• The Steiner tree problem on graphs: inapproximability results
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(4)

• Cabling and transverse simplicity
• scientific article; zbMATH DE number 6318187 (Why is no real title available?)
• The cable trench problem: Combining the shortest path and minimum spanning tree problems
• A multi-objective perspective on the cable-trench problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6048437)