Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T16:02:21.707Z Has data issue: false hasContentIssue false

“Minimax Length Links” of a Dissimilarity Matrix and Minimum Spanning Trees

Published online by Cambridge University Press:  01 January 2025

J. Douglas Carroll*
Affiliation:
Rutgers University
*
Requests for reprints should be sent to J. Douglas Carroll, Faculty of Management, Rutgers University, 181 New Street, Newark, NJ 07102-1895.

Abstract

A theorem is proved stating that the set of all “minimax links”, defined as links minimizing, over paths, the maximum length of links in any path connecting a pair of objects comprising nodes in an undirected weighted graph, comprise the union of all minimum spanning trees of that graph. This theorem is related to methods of fitting network models to dissimilarity data, particularly a method called “Pathfinder” due to Schvaneveldt and his colleagues, as well as to single linkage clustering, and results concerning the relationship between minimum spanning trees and single linkage hierarchical trees.

Information

Type
Original Paper
Copyright
Copyright © 1995 The Psychometric Society

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.)

Article purchase

Temporarily unavailable