Maximum transfer distance between partitions

被引:25
作者
Charon, Irene
Denoeud, Lucile
Guenoche, Alain
Hudry, Olivier
机构
[1] Ecole Natl Super Telecommun Bretagne, F-75634 Paris 13, France
[2] Inst Math Luminy, F-13009 Marseille, France
关键词
partitions; distance; transfer;
D O I
10.1007/s00357-006-0006-2
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper, we study a distance defined over the partitions of a finite set. Given two partitions P and Q, this distance is defined as the minimum number of transfers of an element from one class to another, required to transform P into Q. We recall the algorithm to evaluate this distance and we give some formulae for the maximum distance value between two partitions having exactly or at most p and q classes, for given p and q.
引用
收藏
页码:103 / 121
页数:19
相关论文
共 21 条
[1]  
Ahuja R.K., 1993, NETWORK FLOWS THEORY
[2]   RECENT DIRECTIONS IN NETLIST PARTITIONING - A SURVEY [J].
ALPERT, CJ ;
KAHNG, AB .
INTEGRATION-THE VLSI JOURNAL, 1995, 19 (1-2) :1-81
[3]  
[Anonymous], 2000, THESIS U ULTRECHT
[4]  
Batagelj V, 1999, LECT NOTES COMPUT SC, V1731, P90
[5]   THE COMPLEXITY OF COMPUTING METRIC DISTANCES BETWEEN PARTITIONS [J].
DAY, WHE .
MATHEMATICAL SOCIAL SCIENCES, 1981, 1 (03) :269-287
[6]  
DEFRAYSSEIX H, 1992, ALGORITHMS REV, V2, P105
[7]  
DENOEUD L, 2006, IFCS 2006 C LJUBLJ S
[8]   Coupled two-way clustering analysis of gene microarray data [J].
Getz, G ;
Levine, E ;
Domany, E .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2000, 97 (22) :12079-12084
[9]  
Guénoche A, 2004, ST CLASS DAT ANAL, P15
[10]  
GUENOCHE A, 2005, ALIO EUR C COMB OPT