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

DOI10.1007/S00453-016-0145-8MaRDI QIDQ524378zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, H. Esfandiari, Mohammad T. Hajiaghayi, Rohit Khandekar, Guy Kortsarz, S. Seddighin

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

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

Recommendations

• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Parameterized approximation algorithms for bidirected Steiner network problems

Cites work

• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• A tight lower bound for planar multiway cut with fixed number of terminals
• Approximability of capacitated network design
• Approximation Algorithms for Directed Steiner Problems
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• On the complexity of k-SAT
• Polylogarithmic inapproximability
• Strong computational lower bounds via parameterized complexity
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

Cited in

(6)

• A tight lower bound for planar Steiner orientation
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q524378)