Multicuts in planar and bounded-genus graphs with bounded number of terminals
From MaRDI portal
DOI10.1007/978-3-662-48350-3_32zbMath1371.05285arXiv1502.00911OpenAlexW1876731621MaRDI QIDQ2408168
Publication date: 10 October 2017
Published in: Algorithmica, Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.00911
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ Unnamed Item ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- Planar separators and parallel polygon triangulation.
- A simple algorithm for multicuts in planar graphs with outer terminals
- The planar multiterminal cut problem
- Graph-encoded maps
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- 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
- Shortest Cut Graph of a Surface with Prescribed Vertex Set
- A Separator Theorem for Planar Graphs
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs
- Homology Flows, Cohomology Cuts
- On the History of Combinatorial Optimization (Till 1960)
- Minimum cuts and shortest homologous cycles
- Tightening Nonsimple Paths and Cycles on Surfaces
- Multicut is FPT
- Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Multicuts in planar and bounded-genus graphs with bounded number of terminals
