A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
From MaRDI portal
Publication:2843292
DOI10.1007/978-3-642-31594-7_57zbMath1272.68147OpenAlexW95416648MaRDI QIDQ2843292
Publication date: 12 August 2013
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_57
Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Related Items (17)
FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ A tight lower bound for planar Steiner orientation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Geometric Set Cover for Orthants ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
This page was built for publication: A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
