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
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
