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)
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems, How to Secure Matchings against Edge Failures, 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, Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs, Unnamed Item, Parameterized certificate dispersal and its variants, Node connectivity augmentation via iterative randomized rounding, Solving Steiner trees: Recent advances, challenges, and perspectives, An ETH-tight algorithm for bidirected Steiner connectivity, Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane, Improved approximation algorithms for directed Steiner forest, A tight algorithm for strongly connected Steiner subgraph on two terminals with demands, On the edge capacitated Steiner tree problem, Augmenting weighted graphs to establish directed point-to-point connectivity, The Steiner connectivity problem, Optimal data placement on networks with a constant number of clients, A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract), Locally Semicomplete Digraphs and Generalizations, On Directed Steiner Trees with Multiple Roots
