A near-linear time minimum Steiner cut algorithm for planar graphs

2019/12/23 by Stephen Jue, Philip N. Klein, Jue, Stephen +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques #cs.DS

paper · pdf · doi:10.48550/arxiv.1912.11103

14 pages, 6 figures

openalex publication_date 2019/12/23 · arxiv created 2019/12/31 · arxiv updated 2020/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the Minimum Steiner Cut problem on undirected planar graphs with non-negative edge weights. This problem involves finding the minimum cut of the graph that separates a specified subset X of vertices (terminals) into two parts. This problem is of theoretical interest because it generalizes two classical optimization problems, Minimum s-t Cut and Minimum Cut, and of practical importance because of its application to computing a lower bound for Steiner (Subset) TSP. Our algorithm has running time O(nlognlogk) where k is the number of terminals.

Cited by

• Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes

Related

• Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
• A Simple Algorithm for Minimum Cuts in Near-Linear Time
• Min st-Cut of a Planar Graph in O(n loglog n) Time
• Minimum Cut of Directed Planar Graphs in O(nloglogn) Time
• Planar Multiway Cut with Terminals on Few Faces