Suboptimal cuts: Their enumeration, weight and number. Vazirani, V. & Yannakakis, M. In Proc. of International Colloquium on Automata, Languages and Programming (ICALP 1992), volume 623, of Lect Notes Comput Sci, pages 366–377, 1992.
doi  abstract   bibtex   
We present (1) an algorithm that enumerates the cuts of a network by increasing weight with polynomial delay, and (2) an algorithm that computes the k-th minimum weight in polynomial time for fixed k. We also show that in the case of undirected networks there are only polynomially many cuts that have the k-th minimum weight for any fixed k (whereas directed networks can have exponentially many different minimum cuts).
@InProceedings{vazirani92suboptimal,
  author    = {Vazirani, Vijay and Yannakakis, Mihalis},
  title     = {Suboptimal cuts: Their enumeration, weight and number},
  booktitle = {Proc. of International Colloquium on Automata, Languages and Programming (ICALP 1992)},
  year      = {1992},
  volume    = {623},
  series    = lncs,
  pages     = {366--377},
  publisher = Springer,
  abstract  = {We present (1) an algorithm that enumerates the cuts of a network by increasing weight with polynomial delay, and (2) an algorithm that computes the k-th minimum weight in polynomial time for fixed k. We also show that in the case of undirected networks there are only polynomially many cuts that have the k-th minimum weight for any fixed k (whereas directed networks can have exponentially many different minimum cuts).},
  doi       = {10.1007/3-540-55719-9_88},
  keywords  = {mincut; minimum cut; enumeration; suboptimal cuts},
  owner     = {Sebastian},
  timestamp = {2011.04.07},
}

Downloads: 0