Unbalanced Graph Cuts

Ara Hayrapetyan, David Kempe, Martin Pál, Zoya SvitkinaESA 2005 · OpenReview

Abstract

We introduce the Minimum-size bounded-capacity cut (MinSBCC) problem, in which we are given a graph with an identified source and seek to find a cut minimizing the number of nodes on the source side, subject to the constraint that its capacity not exceed a prescribed bound B. Besides being of interest in the study of graph cuts, this problem arises in many practical settings, such as in epidemiology, disaster control, military containment, as well as finding dense subgraphs and communities in graphs.
BibTeX
@inproceedings{hayrapetyan2005unbalanced,
  author = {Ara Hayrapetyan and David Kempe and Martin Pál and Zoya Svitkina},
  title = {{Unbalanced Graph Cuts}},
  booktitle = {ESA},
  year = {2005},
  url = {https://openreview.net/forum?id=foMsJv0051},
}

Loading related content...

Figure