Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

DOI10.1137/1.9781611973402.129zbMath1421.68112arXiv1911.13161OpenAlexW2989902795MaRDI QIDQ5384091

Rajesh Chitnis, Dániel Marx, Mohammad Taghi Hajiaghayi

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (11)

A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ A tight lower bound for planar Steiner orientation ⋮ Unnamed Item ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

This page was built for publication: Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)