A polynomial-time approximation scheme for planar multiway cut
Lists
Only you see this
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.
BibTeX
@inproceedings{bateni2012polynomial,
author = {MohammadHossein Bateni and MohammadTaghi Hajiaghayi and Philip N. Klein and Claire Mathieu},
title = {{A polynomial-time approximation scheme for planar multiway cut}},
booktitle = {SODA},
year = {2012},
url = {https://openreview.net/forum?id=JzJ8WQPQB6},
}Loading related content...