THE MINIMUM SPANNING TREE PROBLEM IN ARCHAEOLOGY

The minimum spanning tree problem is a well-knowm problem of combinato rial optimization. It was independently discovered in archaeology by R enfrew and Sterud in their method of close proximity analysis. Unlike traditional methods of seriation, this method permits branching struct ures that reveal clustering in archaeological data. Identifying close proximity analysis as the minimum spanning tree problem permits a more efficient means of computation, an explicit rule of clustering, and r ecognition of problems of indeterminacy in the analysis of network dat a. These points are illustrated with reference to Irwin's recent study of voyaging and cultural similarity in Polynesia.