Partition-distance: A problem and class of perfect graphs arising in clustering. (English) Zbl 1013.68142

Summary: Partitioning of a set of elements into disjoint clusters is a fundamental problem that arises in many applications. Different methods produce different partitions, so it is useful to have a measure of the similarity, or distance, between two or more partitions. In this paper we examine one distance measure used in a clustering application in computational genetics. We show how to efficiently compute the distance, and how this defines a new class of perfect graphs.


68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Full Text: DOI


[1] Almudevar, A.; Field, C., Estimation of single generation sibling relationships based on DNA markers, J. agricultural, biological environment. statist., 4, 136-165, (1999)
[2] Brandstadt, A.; Le, V.B.; Spinrad, J.P., Graph classes — A survey, SIAM monographs on discrete math. appl., 3, (1999), SIAM
[3] Cook, W.; Cunningham, W.; Pulleyblank, W.; Schrijver, A., Combinatorial optimization, (1998), Wiley-Interscience Publications New York
[4] Garey, M.; Johnson, D., Computers and intractability, (1979), Freeman San Francisco, CA
[5] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[6] Grotschel, M.; Lovasz, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056
[7] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0358.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.