@InProceedings{dahlhaus92complexity,
  author    = {Dahlhaus, E. and Johnson, D. S. and Papadimitriou, C. H. and Seymour, P. D. and Yannakakis, M.},
  title     = {The complexity of multiway cuts (extended abstract)},
  booktitle = {Proc. of ACM Symposium on Theory Of Computing (STOC 1992)},
  year      = {1992},
  pages     = {241--251},
  publisher = {ACM press, New York},
  abstract  = {In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2{\"{\i}}{\textquestiondown}{\oe}2/k of the optimal cut weight.},
  doi       = {10.1145/129712.129736},
  isbn      = {0-89791-511-9},
  location  = {Victoria, British Columbia, Canada},
  owner     = {Sebastian},
  timestamp = {2010.10.19},
}

{"_id":"ewNvTvjiGW3Wb8NMo","bibbaseid":"dahlhaus-johnson-papadimitriou-seymour-yannakakis-thecomplexityofmultiwaycutsextendedabstract-1992","authorIDs":[],"author_short":["Dahlhaus, E.","Johnson, D. S.","Papadimitriou, C. H.","Seymour, P. D.","Yannakakis, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Dahlhaus"],"firstnames":["E."],"suffixes":[]},{"propositions":[],"lastnames":["Johnson"],"firstnames":["D.","S."],"suffixes":[]},{"propositions":[],"lastnames":["Papadimitriou"],"firstnames":["C.","H."],"suffixes":[]},{"propositions":[],"lastnames":["Seymour"],"firstnames":["P.","D."],"suffixes":[]},{"propositions":[],"lastnames":["Yannakakis"],"firstnames":["M."],"suffixes":[]}],"title":"The complexity of multiway cuts (extended abstract)","booktitle":"Proc. of ACM Symposium on Theory Of Computing (STOC 1992)","year":"1992","pages":"241–251","publisher":"ACM press, New York","abstract":"In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2ï¿œ2/k of the optimal cut weight.","doi":"10.1145/129712.129736","isbn":"0-89791-511-9","location":"Victoria, British Columbia, Canada","owner":"Sebastian","timestamp":"2010.10.19","bibtex":"@InProceedings{dahlhaus92complexity,\n author = {Dahlhaus, E. and Johnson, D. S. and Papadimitriou, C. H. and Seymour, P. D. and Yannakakis, M.},\n title = {The complexity of multiway cuts (extended abstract)},\n booktitle = {Proc. of ACM Symposium on Theory Of Computing (STOC 1992)},\n year = {1992},\n pages = {241--251},\n publisher = {ACM press, New York},\n abstract = {In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is simply the min-cut, max-flow problem, and can be solved in polynomial time. We show that the problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed k. The planar problem is NP-hard, however, if k is not fixed. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2{\\\"{\\i}}{\\textquestiondown}{\\oe}2/k of the optimal cut weight.},\n doi = {10.1145/129712.129736},\n isbn = {0-89791-511-9},\n location = {Victoria, British Columbia, Canada},\n owner = {Sebastian},\n timestamp = {2010.10.19},\n}\n\n","author_short":["Dahlhaus, E.","Johnson, D. S.","Papadimitriou, C. H.","Seymour, P. D.","Yannakakis, M."],"key":"dahlhaus92complexity","id":"dahlhaus92complexity","bibbaseid":"dahlhaus-johnson-papadimitriou-seymour-yannakakis-thecomplexityofmultiwaycutsextendedabstract-1992","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:41.812Z","downloads":0,"keywords":[],"search_terms":["complexity","multiway","cuts","extended","abstract","dahlhaus","johnson","papadimitriou","seymour","yannakakis"],"title":"The complexity of multiway cuts (extended abstract)","year":1992,"dataSources":["C5FtkvWWggFfMJTFX"]}