A tight algorithm for strongly connected Steiner subgraph on two terminals with demands

DOI10.1007/s00453-016-0145-8zbMath1364.68225OpenAlexW2228622483MaRDI QIDQ524378

Mohammad Taghi Hajiaghayi, Guy Kortsarz, Hossein Esfandiari, Saeed Seddighin, Rajesh Chitnis, Rohit Khandekar

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://pure-oai.bham.ac.uk/ws/files/90683134/J5_A_Tight_Algorithm_for_Strongly.pdf

zbMATH Keywords

directed graphsexponential time hypothesisFPT algorithmsstrongly connected Steiner subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A tight lower bound for planar Steiner orientation ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

Cites Work

• Unnamed Item
• Strong computational lower bounds via parameterized complexity
• A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• 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
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Polylogarithmic inapproximability
• Approximation Algorithms for Directed Steiner Problems
• Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
• On the complexity of \(k\)-SAT

This page was built for publication: A tight algorithm for strongly connected Steiner subgraph on two terminals with demands