Multicuts in planar and bounded-genus graphs with bounded number of terminals

DOI10.1007/978-3-662-48350-3_32zbMath1371.05285arXiv1502.00911OpenAlexW1876731621MaRDI QIDQ2408168

Éric Colin de Verdière

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

zbMATH Keywords

algorithmsurfaceembeddingplanar graphcomputational topologymulticut

Mathematics Subject Classification ID

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