Paper Info
Title
A polynomial-time approximation scheme for planar multiway cut
Abstract
Given an undirected graph with edge lengths and a subset of nodes (called the terminals), the multiway cut (also called the multi-terminal cut) problem asks for a subset of edges, with minimum total length, whose removal disconnects each terminal from all others. The problem generalizes minimum s-t cut, but is NP-hard for planar graphs and APX-hard for general graphs [11]. In this paper, we present a PTAS for multiway cut on planar graphs.
Year
DOI
Venue
2012
10.5555/2095116.2095170
SODA
Keywords
Field
DocType
general graph,edge length,planar multiway cut,polynomial-time approximation scheme,planar graph,undirected graph,multi-terminal cut,minimum s-t cut,multiway cut,minimum total length
Cut,Discrete mathematics,Graph,Combinatorics,Minimum cut,Planar,Gomory–Hu tree,Polynomial-time approximation scheme,Planar graph,Mathematics,Maximum cut
Conference
ISBN
Citations 
PageRank 
978-1-61197-251-1
9
0.51
References 
Authors
27
4
Name
Order
Citations
PageRank
MohammadHossein Bateni128621.45
MohammadTaghi Hajiaghayi23082201.38
Philip N. Klein32681256.19
Claire Mathieu445225.78