A polynomial-time approximation scheme for planar multiway cut
From MaRDI portal
Recommendations
Cites work
- A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- A simple algorithm for multicuts in planar graphs with outer terminals
- A subset spanner for Planar graphs, with application to subset TSP
- An O(n n) approximation scheme for Steiner tree in planar graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
- Finding minimum-quotient cuts in planar graphs
- scientific article; zbMATH DE number 6381762 (Why is no real title available?)
- scientific article; zbMATH DE number 1342124 (Why is no real title available?)
- scientific article; zbMATH DE number 2081002 (Why is no real title available?)
- scientific article; zbMATH DE number 1775387 (Why is no real title available?)
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
- Subgraph Isomorphism in Planar Graphs and Related Problems
- The Complexity of Multiterminal Cuts
- The planar multiterminal cut problem
Cited in
(21)- An improved approximation algorithm of MULTIWAY CUT.
- _p-norm multiway cut
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- A simple algorithm for the planar multiway cut problem
- The cutting plane method is polynomial for perfect matchings
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- A tight lower bound for planar multiway cut with fixed number of terminals
- scientific article; zbMATH DE number 4195169 (Why is no real title available?)
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
- A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
- scientific article; zbMATH DE number 7559431 (Why is no real title available?)
- A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
- A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
- Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
- Simplex partitioning via exponential clocks and the multiway cut problem
- Correlation clustering and two-edge-connected augmentation for planar graphs
- \(\ell_p\)-norm multiway cut
This page was built for publication: A polynomial-time approximation scheme for planar multiway cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743427)
