Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-27T17:00:14.387Z Has data issue: false hasContentIssue false
  • English
  • Français

The Minimum Spanning Tree Problem in Archaeology

Published online by Cambridge University Press:  20 January 2017

Per Hage ,
Frank Harary  and
Brent James
Per Hage
Affiliation:
Department of Anthropology, University of Utah, Salt Lake City, UT 84112
Frank Harary
Affiliation:
Department of Computer Science, New Mexico State University, Las Cruces, NM 88003–0001
Brent James
Affiliation:
Department of Biostatistics, Harvard School of Public Health, Cambridge, MA 02138
Get access Rights & Permissions [Opens in a new window]

Abstract

The minimum spanning tree problem is a well-known problem of combinatorial optimization. It was independently discovered in archaeology by Renfrew and Sterud in their method of close proximity analysis. Unlike traditional methods of seriation, this method permits branching structures 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 a recognition of problems of indeterminacy in the analysis of network data. These points are illustrated with reference to Irwin's recent study of voyaging and cultural similarity in Polynesia.

Resumen

Resumen

El problema del árbol de expansión mínima es bien conocido en optimizatión combinatorial. Este problema fue descubierto independientemente en la arqueología cuando Renfrew y Sterud aplicaron su análisis de “close proximity.” Este método es diferente de métodos tradicionales de seriación porque trabaja con estructuras dendríticas que muestran racemización en datos arqueológicos. El identificar el análisis de “close proximity” como el problema del árbol de expansión mínima permite (I) la aplicación de técnicas de computatión más eficientes, (2) el uso de una regla explícita de racemización, y (3) un reconocimento de los problemas indeterminados en el andlisis de datos de red. Comparamos este metodo con la obra reciente de Irwin sobre la navegación en barco y la similitud de culturas en Polinesia.

Type
Reports
Information
American Antiquity , Volume 61 , Issue 1 , January 1996 , pp. 149 - 155
Copyright
Copyright © The Society for American Archaeology 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

References Cited

Bellwood, P. 1987 The Polynesians: Prehistory of an Island People. Thames and Hudson, London.Google Scholar
Boruvka, O. 1926a O jistem problemu minimalnim. Acta Societatis Scientarium Naturalium Moravicae 3: 37–58.Google Scholar
Boruvka, O. 1926b Prlspevek k reseni otazky ekonomicke stavby electrovodnich siti. Eletrotechnicky Obzor 15: 153–154.Google Scholar
Brainerd, G. W. 1951 The Place of Chronological Ordering in Archaeological Analysis. American Antiquity 16: 301–313.Google Scholar
Buckley, E, and Harary, E 1990 Distance in Graphs. Addison-Wesley, Reading, Massachusetts.Google Scholar
Burrows, E. G. 1938 Western Polynesia: A Study of Cultural Differentiation. Ethnologiska Studier 7, Goteborg, Sweden.Google Scholar
Friedman, J. 1981 Notes on Structure and History in Oceania. Folk 23: 275–295.Google Scholar
Graham, R. L., and Hell, P. 1985 On the History of the Minimum Spanning Tree Problem. Annals of the History of Computing 7: 43–57.Google Scholar
Grofman, B., and Landa, J. T. 1983 The Development of Trading Networks among Spatially Separated Traders as a Process of Proto-Coalition Formation: The Kula Trade. Social Networks 5: 347–365.Google Scholar
Guiart, J. 1963 Un etat palatial Oceanien: l'Empire maritime des Tu'i Tonga. Appendix to Structure de la Chejferie en Melanesie du Sud. Travaux et Memoires, no. 66. Institut d'Ethnologie, Paris.Google Scholar
Hage, P., and Harary, F. 1991 Exchange in Oceania. Clarendon Press, Oxford.Google Scholar
Hage, P., and Harary, F. 1996 Island Networks. Cambridge University Press, Cambridge. in press.Google Scholar
Irwin, G. 1992 The Prehistoric Exploration and Colonisation of the Pacific. Cambridge University Press, Cambridge.Google Scholar
Kirch, P. V 1984 The Evolution of the Polynesian Chiefdoms. Cambridge University Press, Cambridge.Google Scholar
Kirch, P. V 1988 Niautoputapu: The Prehistory of an Island Chiefdom. Burke Museum, Seattle.Google Scholar
Kirch, P. V, and Green, R. C. 1987 History, Phytogeny, and Evolution in Polynesia. Current Anthropology 28: 431–56.CrossRefGoogle Scholar
Kruskal, J. B. 1956 On the Shortest Spanning Tree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7: 48–50.Google Scholar
Lewis, D. 1972 We the Navigators. University of Hawaii Press, Honolulu.CrossRefGoogle Scholar
Pawley, A., and Green, R. C. 1975 Dating the Dispersal of the Oceanic Languages. Oceanic Linguistics 12: 1–68.Google Scholar
Prim, R. C. 1957 Shortest Connection Networks and Some Generalizations. Bell System Technical Journal 36: 1389–1401.Google Scholar
Prim, R. C. 1986 Peer Polity Interaction and Socio-political Change. Cambridge University Press, Cambridge.Google Scholar
Renfrew, C., and Sterud, G. 1969 Close-Proximity Analysis: A Rapid Method for the Ordering of Archaeological Materials. American Antiquity 34: 265–277.CrossRefGoogle Scholar
Robinson, W. S. 1951 A Method for Chronologically Ordering Archaeological Deposits. American Antiquity 16: 293–301.CrossRefGoogle Scholar
Wilson, R. J., and Watkins, J. J. 1990 Graphs: An Introductory Approach. John Wiley and Sons, New York.Google Scholar