Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
From MaRDI portal
Publication:2843281
DOI10.1007/978-3-642-31594-7_48zbMath1272.68157OpenAlexW1523762238MaRDI QIDQ2843281
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_48
Analysis of algorithms and problem complexity (68Q25) 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 (16)
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams ⋮ 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 ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Coloring Graphs with Constraints on Connectivity ⋮ Quick separation in chordal and split graphs ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
This page was built for publication: Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
