On the edge capacitated Steiner tree problem

DOI10.1016/j.disopt.2020.100607zbMath1506.68066arXiv1607.07082OpenAlexW3069417356MaRDI QIDQ2218647

Marie-Christine Costa, Cédric Bentz, Alain Hertz

Publication date: 15 January 2021

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.07082

zbMATH Keywords

computational complexityapproximation algorithmsSteiner treescapacity constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Robust capacitated Steiner trees and networks with uniform demands ⋮ Models of random subtrees of a graph ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ Formulations for designing robust networks. An application to wind power collection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On shortest disjoint paths in planar graphs
• On the maximum disjoint paths problem on edge-colored graphs
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
• A simplified NP-complete satisfiability problem
• The Steiner problem with edge lengths 1 and 2
• The directed subgraph homeomorphism problem
• Finding minimum cost directed trees with demands and capacities
• The Steiner tree problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• The \((K, k)\)-capacitated spanning tree problem
• Advances in Steiner trees
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• Dioïds and semirings: Links to fuzzy sets and other applications
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• An improved LP-based approximation for steiner tree
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Min-Sum 2-Paths Problems
• On Fixed Cost k-Flow Problems
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The complexity of the capacitated tree problem
• Shortest Two Disjoint Paths in Polynomial Time
• The steiner problem in graphs
• Algorithms - ESA 2003
• Optimizing the Design of a Wind Farm Collection Network

This page was built for publication: On the edge capacitated Steiner tree problem