Solving Planar k -Terminal Cut in O(n^{c \sqrt{k}}) Time

DOI10.1007/978-3-642-31594-7_48MaRDI QIDQ2843281zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Philip N. Klein

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2081002
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Revisiting a simple algorithm for the planar multiterminal cut problem
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• A polynomial-time approximation scheme for planar multiway cut
• The planar multiterminal cut problem
• Solving minimum K-cardinality cut problems in planar graphs
• scientific article; zbMATH DE number 6469225
• A tight lower bound for planar multiway cut with fixed number of terminals
• scientific article; zbMATH DE number 4195169

Cited in

(26)

• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• A tight lower bound for planar multiway cut with fixed number of terminals
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• scientific article; zbMATH DE number 2081002 (Why is no real title available?)
• Coloring Graphs with Constraints on Connectivity
• Parameterized approximation algorithms for bidirected Steiner network problems
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Almost tight lower bounds for hard cutting problems in embedded graphs
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Quick separation in chordal and split graphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• 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
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
• Two-sets cut-uncut on planar graphs
• Edge multiway cut and node multiway cut are hard for planar subcubic graphs
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Compound logics for modification problems
• Robust contraction decomposition for minor-free graphs and its applications
• Improved parameterized and exact algorithms for cut problems on trees
• Revisiting a simple algorithm for the planar multiterminal cut problem

This page was built for publication: Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time

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