Partition-distance: A problem and class of perfect graphs arising in clustering

被引：103

作者：

Gusfield, D ^{[1
]}

机构：

[1] Univ Calif Davis, Dept Comp Sci, Davis, CA 95616 USA

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 82卷 / 03期

基金：

美国国家科学基金会;

关键词：

partitioning; clustering; assignment problem; node cover; perfect graph; genetics; graph algorithms; combinatorial problems;

D O I：

10.1016/S0020-0190(01)00263-0

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：159 / 164

页数：6

共 7 条

[1] Estimation of single-generation sibling relationships based on DNA markers [J].