A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
From MaRDI portal
Publication:2946016
DOI10.1007/978-3-319-13524-3_14zbMath1364.68224arXiv1506.03760OpenAlexW196127575MaRDI QIDQ2946016
Rohit Khandekar, Rajesh Chitnis, Hossein Esfandiari, Saeed Seddighin, Mohammad Taghi Hajiaghayi, Guy Kortsarz
Publication date: 15 September 2015
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.03760
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
Cites Work
- Unnamed Item
- Strong computational lower bounds via parameterized complexity
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
- Approximability of Capacitated Network Design
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Polylogarithmic inapproximability
- Approximation Algorithms for Directed Steiner Problems
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
This page was built for publication: A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)