A simple enhancement of the Esau–Williams heuristic for the capacitated minimum spanning tree problem

G Bruno and G Laporte ()
Additional contact information
G Bruno: Università di Napoli
G Laporte: GERAD and École des Hautes Études Commerciales

Journal of the Operational Research Society, 2002, vol. 53, issue 5, 583-586

Abstract: Abstract 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.

Keywords: capacitated minimum spanning trees; modified Esau–Williams heuristic (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601246 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:53:y:2002:i:5:d:10.1057_palgrave.jors.2601246

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601246

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().