Complexity of the Steiner Network Problem with Respect to the Number of Terminals
From MaRDI portal
Publication:5090473
DOI10.4230/LIPIcs.STACS.2019.25OpenAlexW2963676274MaRDI QIDQ5090473
Dušan Knop, Ondřej Suchý, Eduard Eiben, Fahad Panolan
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1802.08189
planar graphsparameterized algorithmsexponential time hypothesisbounded genusdirected Steiner network
Related Items (2)
Preference swaps for the stable matching problem ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Elements of finite model theory.
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem
- Steiner minimal trees
- Diameter and treewidth in minor-closed graph families
- Dynamic programming for minimum Steiner trees
- On tree width, bramble size, and expansion
- Design networks with bounded pairwise distance
- Graph Theory
- Set connectivity problems in undirected graphs and the directed steiner network problem
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
- Fourier meets M\"{o}bius: fast subset convolution
- Polylogarithmic inapproximability
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Approximation Algorithms for Directed Steiner Problems
- On Problems as Hard as CNF-SAT
- ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
- Reducibility among Combinatorial Problems
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- Steiner Tree Approximation via Iterative Randomized Rounding
- The steiner problem in graphs
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
- On the complexity of \(k\)-SAT
This page was built for publication: Complexity of the Steiner Network Problem with Respect to the Number of Terminals
