A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals
From MaRDI portal
Publication:5149755
DOI10.1137/18M1183297zbMath1458.05244arXiv1611.02966OpenAlexW2565287168MaRDI QIDQ5149755
Éric Colin de Verdière, Vincent Cohen-Addad, Arnaud de Mesmay
Publication date: 8 February 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.02966
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Splitting (complicated) surfaces is hard
- Intersections of curves on surfaces
- Making curves minimally crossing by Reidemeister moves
- Optimally cutting a surface into a disk
- Systems of curves on surfaces
- Faster algorithm for optimum Steiner trees
- Multicuts in planar and bounded-genus graphs with bounded number of terminals
- On the hardness of approximating Multicut and Sparsest-Cut
- Curves von 2-manifolds and isotopies
- 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
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Shortest Cut Graph of a Surface with Prescribed Vertex Set
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- The Complexity of Multiterminal Cuts
- Approximating Multicut and the Demand Graph
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Homology Flows, Cohomology Cuts
- Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
- Excluded minors, network decomposition, and multicommodity flow
- On the History of Combinatorial Optimization (Till 1960)
- Minimum cuts and shortest homologous cycles
- Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
- Tightening Nonsimple Paths and Cycles on Surfaces
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Improved algorithms for min cut and max flow in undirected planar graphs
- Multicut is FPT
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- The steiner problem in graphs
- Multi-Commodity Network Flows
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Faster shortest-path algorithms for planar graphs
