A NEW AND IMPROVED ALGORITHM FOR THE 3-CUT PROBLEM

Authors
BURLET M GOLDSCHMIDT O
Citation
M. Burlet et O. Goldschmidt, A NEW AND IMPROVED ALGORITHM FOR THE 3-CUT PROBLEM, Operations research letters, 21(5), 1997, pp. 225-227
Citations number
5
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
21
Issue
5
Year of publication
1997
Pages
225 - 227
Database
ISI
SICI code
0167-6377(1997)21:5<225:ANAIAF>2.0.ZU;2-1
Abstract
We present a O(mn(3)) time exact algorithm for finding a minimum 3-cut in an edge-weighted graph. This running time compares very favorably with the best-known algorithm which takes O(mn(5)) time in the worst c ase. (C) 1997 Elsevier Science B.V. All rights reserved.