Cut tree algorithms: An experimental study

Authors
Goldberg, AV Tsioutsiouliklis, K
Citation
Av. Goldberg et K. Tsioutsiouliklis, Cut tree algorithms: An experimental study, J ALGORITHM, 38(1), 2001, pp. 51-83
Citations number
18
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF ALGORITHMS
ISSN journal
01966774 → ACNP
Volume
38
Issue
1
Year of publication
2001
Pages
51 - 83
Database
ISI
SICI code
0196-6774(200101)38:1<51:CTAAES>2.0.ZU;2-P
Abstract
This is an experimental study of algorithms for the cut tree problem. We st udy the Gomory-Hu and Gusfield algorithms as well as heuristics aimed to ma ke the former algorithm faster. We develop an efficient implementation of t he Gomory-Hu algorithm. Wt: also develop problem families for testing cut t ree algorithms. In our tests, the Gomory-Hu algorithm with a right combinat ion of heuristics was significantly more robust than Gusfield's algorithm. (C) 2001 Academic Press.