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

DOI10.1007/s00453-016-0258-0zbMath1371.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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item