A Fuzzy Relation Approach to Single Linkage

Maman A. Djauhari


Single linkage is equivalent to sub-dominant ultrametric. Many algorithms are available for constructing these two objects. But all of then, except one which was proposed by Gondran, are very tedious because of the lack of algebraic structure. Gondran used a special algebraic system as theoretical bases. But it seems rather artificial. In this paper, we propose a more formal approach based on fuzzy relation. The main result presented here is the equivalence between sub-dominant ultrametric and the min-max transitive closure of a symmetric and anti reflexive fuzzy relation. This property enables us to construct an easy and efficient algorithm. At the end of this paper we will find its relationship with Gondran's approach.


single linkage; sub-dominant ultametric and Gondran’s algebraic system;

Full Text:



Benzecri J.P. L’analyse des donnees; la taxinomie, Dunod – Paris, 1980.

Caillez F. and Pages J.P. Introduction a l’ analyse des donnees, Smash – Paris, 1976.

Jambu M. Classification automatique pour l’ analyse des donnees. Dunod – Paris 1978.

Kaufmann A. Introduction a la theorie des sousensemble flous; element theoriques de base. 2eme edition. Masson Paris 1977.

Kaufmann A. Introduction a la theorie des sousensemble flous; application a la classification et a la reconnaissance des formes aux automates et aux system; aux choix des criteres. Masson – Paris 1975.

Jardine N. and Sibson P. Mathematical taxonomy. John Wiley and Sons 1977.

Pal S.K. and Majumder D.K.D. Fuzzy Mathematical approach to pattern recognition. Wiley Eastern Ltd 1986.

Roux. Classification automatique. Ecole d’ Ete d’ Analyse Numerique, Paris 1975.

Van Cutsem B. Ultrametrique, distance, o – distances maximum dominees par une dissimilarite donnee. Statistique et Analyse des Donnees, Vol 8 No. 2, 1983.


  • There are currently no refbacks.

View my Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.


Lembaga Penelitian dan Pengabdian kepada Masyarakat (LPPM), Center for Research and Community Services (CRCS) Building, 6th & 7th Floor, Institut Teknologi Bandung, Jalan Ganesha 10, Bandung 40132, Indonesia, Tel. +62-22-86010080, Fax.: +62-22-86010051; E-mail: jmfs@lppm.itb.ac.id