On the edge capacitated Steiner tree problem

DOI10.1016/J.DISOPT.2020.100607MaRDI QIDQ2218647zbMATH OpenOpenAlexFDO

Authors Cédric Bentz, Marie-Christine Costa, 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

approximation algorithmscapacity constraintscomputational complexitySteiner trees

Mathematics Subject Classification ID

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

Abstract: Given a graph G = (V,E) with a root r in V, positive capacities {c(e)|e in E}, and non-negative lengths {l(e)|e in E}, the minimum-length (rooted) edge capacitated Steiner tree problem is to find a tree in G of minimum total length, rooted at r, spanning a given subset T of vertices, and such that, for each e in E, there are at most c(e) paths, linking r to vertices in T, that contain e. We study the complexity and approximability of the problem, considering several relevant parameters such as the number of terminals, the edge lengths and the minimum and maximum edge capacities. For all but one combinations of assumptions regarding these parameters, we settle the question, giving a complete characterization that separates tractable cases from hard ones. The only remaining open case is proved to be equivalent to a long-standing open problem. We also prove close relations between our problem and classical Steiner tree as well as vertex-disjoint paths problems.

Recommendations

• scientific article; zbMATH DE number 1834686
• On full bottleneck Steiner tree problem
• scientific article; zbMATH DE number 1182759
• Steiner tree problems
• Steiner tree problems
• Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
• The Steiner tree problem
• On the full and bottleneck full Steiner tree problems
• On the Euclidean bottleneck full Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem

Cites work

• A simplified NP-complete satisfiability problem
• Advances in Steiner trees
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
• An improved LP-based approximation for Steiner tree
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Dioïds and semirings: Links to fuzzy sets and other applications
• Finding minimum cost directed trees with demands and capacities
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1303557 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2119644 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• Min-sum 2-paths problems
• Network flows. Theory, algorithms, and applications.
• On fixed cost \(k\)-flow problems
• On shortest disjoint paths in planar graphs
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• On the maximum disjoint paths problem on edge-colored graphs
• Optimizing the Design of a Wind Farm Collection Network
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• Shortest two disjoint paths in polynomial time
• Steiner tree problems in computer communication networks.
• The \((K, k)\)-capacitated spanning tree problem
• The complexity of the capacitated tree problem
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• The directed subgraph homeomorphism problem
• The steiner problem in graphs
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(8)

• Formulations for designing robust networks. An application to wind power collection
• The \((K, k)\)-capacitated spanning tree problem
• Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
• The capacity formulation of the capacitated edge activation problem
• 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
• An extended formulation with valid inequalities for the capacitated Steiner arborescence problem

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

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