The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
From MaRDI portal
Publication:3434998
DOI10.1137/S0097539704441241zbMath1118.05039MaRDI QIDQ3434998
Publication date: 3 May 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (21)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ On Directed Steiner Trees with Multiple Roots ⋮ A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Improved approximation algorithms for directed Steiner forest ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane ⋮ The Steiner connectivity problem ⋮ On the edge capacitated Steiner tree problem ⋮ Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs ⋮ Optimal data placement on networks with a constant number of clients ⋮ How to Secure Matchings against Edge Failures ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ Parameterized certificate dispersal and its variants ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ How to Secure Matchings Against Edge Failures ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Unnamed Item
This page was built for publication: The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
