On the edge capacitated Steiner tree problem
From MaRDI portal
Publication:2218647
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
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
