A polynomial-time approximation scheme for planar multiway cut

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire MathieuSODA 2012 · OpenReview

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...

Figure