𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cut Tree Algorithms: An Experimental Study

✍ Scribed by Andrew V Goldberg; Kostas Tsioutsiouliklis

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
654 KB
Volume
38
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

This is an experimental study of algorithms for the cut tree problem. We study the Gomory-Hu and Gusfield algorithms as well as heuristics aimed to make the former algorithm faster. We develop an efficient implementation of the Gomory-Hu algorithm. We also develop problem families for testing cut tree algorithms. In our tests, the Gomory-Hu algorithm with a right combination of heuristics was significantly more robust than Gusfield's algorithm.

πŸ“œ SIMILAR VOLUMES

An Improved Approximation Algorithm for
An Improved Approximation Algorithm for MULTIWAY CUT
✍ Gruia CΔƒlinescu; Howard Karloff; Yuval Rabani πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 132 KB

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due

Computerized pattern cutting: Methods ba
Computerized pattern cutting: Methods based on an isometric tree
✍ JR Manning πŸ“‚ Article πŸ“… 1980 πŸ› Elsevier Science 🌐 English βš– 415 KB

This paper is concerned with the problem of mapping a curved surface onto a plane, with special reference to shoe manufacture. A class of mappings based on an~ isometric tree is investigated and an optimal mapping is defined. A patented method of computerized pattern cutting is also discussed.