A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

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

Mathematics Subject Classification ID

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)