FPT Inapproximability of Directed Cut and Connectivity Problems

DOI10.4230/LIPICS.IPEC.2019.8MaRDI QIDQ5875540zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, Andreas Emil Feldmann

Publication date 3 February 2023

Full work available at URL https://arxiv.org/abs/1910.01934

zbMATH Keywords

connectivitycutsdirected graphsFPT inapproximabilitySteiner problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cited in

(3)

• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• A survey of parameterized algorithms and the complexity of edge modification
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands

This page was built for publication: FPT Inapproximability of Directed Cut and Connectivity Problems

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