| Article ID: | iaor20031146 |
| Country: | United Kingdom |
| Volume: | 53 |
| Issue: | 5 |
| Start Page Number: | 583 |
| End Page Number: | 586 |
| Publication Date: | May 2002 |
| Journal: | Journal of the Operational Research Society |
| Authors: | Laporte Gilbert, Bruno G. |
The Esau–Williams algorithm is one of the best known heuristics for the capacitated minimum spanning tree problem. This paper describes a simple enhancement of this heuristic. On benchmark test problems, the modified method does not result in much larger computation times and almost always produces lower solution values than does the Esau–Williams algorithm. The improvements are often significant.