@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},
}

{"_id":"mqwQ8dd9KgKpccWEM","bibbaseid":"vazirani-yannakakis-suboptimalcutstheirenumerationweightandnumber-1992","authorIDs":[],"author_short":["Vazirani, V.","Yannakakis, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Vazirani"],"firstnames":["Vijay"],"suffixes":[]},{"propositions":[],"lastnames":["Yannakakis"],"firstnames":["Mihalis"],"suffixes":[]}],"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":"Lect Notes Comput Sci","pages":"366–377","publisher":"Springer, Berlin","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","bibtex":"@InProceedings{vazirani92suboptimal,\n author = {Vazirani, Vijay and Yannakakis, Mihalis},\n title = {Suboptimal cuts: Their enumeration, weight and number},\n booktitle = {Proc. of International Colloquium on Automata, Languages and Programming (ICALP 1992)},\n year = {1992},\n volume = {623},\n series = lncs,\n pages = {366--377},\n publisher = Springer,\n 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).},\n doi = {10.1007/3-540-55719-9_88},\n keywords = {mincut; minimum cut; enumeration; suboptimal cuts},\n owner = {Sebastian},\n timestamp = {2011.04.07},\n}\n\n","author_short":["Vazirani, V.","Yannakakis, M."],"key":"vazirani92suboptimal","id":"vazirani92suboptimal","bibbaseid":"vazirani-yannakakis-suboptimalcutstheirenumerationweightandnumber-1992","role":"author","urls":{},"keyword":["mincut; minimum cut; enumeration; suboptimal cuts"],"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.777Z","downloads":0,"keywords":["mincut; minimum cut; enumeration; suboptimal cuts"],"search_terms":["suboptimal","cuts","enumeration","weight","number","vazirani","yannakakis"],"title":"Suboptimal cuts: Their enumeration, weight and number","year":1992,"dataSources":["C5FtkvWWggFfMJTFX"]}