caa a22 4500 475769708 CHVBK 20180406123616.0 cr unu---uuuuu 170329e20000901xx s 000 0 eng 10.1007/PL00011383 doi (NATIONALLICENCE)springer-10.1007/PL00011383 A fast algorithm for computing minimum 3-way and 4-way cuts [Elektronische Daten] [Hiroshi Nagamochi, Toshihide Ibaraki] Abstract. : For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n k-1 F(n,m))=O(mn k log(n 2 /m)) time and O(n 2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound Õ(mn 3) for weighted graphs, but improves the bound Õ(mn 3) to O(n 2 F(n,m))=O(min{mn 8/3,m 3/2 n 2}) for unweighted graphs. The bound Õ(mn 4) for k=4 improves the previous best randomized bound Õ(n 6) (for m=o(n 2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Springer-Verlag Berlin Heidelberg, 2000 Key words: minimum cuts - graphs - hypergraphs -k-way cuts - polynomial algorithm - submodular function nationallicence Nagamochi Hiroshi Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku, Toyohashi, Aichi 441-8580 Japan, e-mail: naga@ics.tut.ac.jp, JP aut Ibaraki Toshihide Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-8501 Japan, e-mail: ibaraki@i.kyoto-u.ac.jp, JP aut https://doi.org/10.1007/PL00011383 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/PL00011383 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Nagamochi Hiroshi Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku, Toyohashi, Aichi 441-8580 Japan, e-mail: naga@ics.tut.ac.jp, JP aut NATIONALLICENCE 700 1- Ibaraki Toshihide Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-8501 Japan, e-mail: ibaraki@i.kyoto-u.ac.jp, JP aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer