Graph partitioning using linear and semidefinite programming

被引：43
作者：
Lisser, A
Rendl, E
机构：
[1] Univ Paris 11, Rech Informat Lab, F-91405 Orsay, France
[2] Univ Klagenfurt, Inst Math, A-9020 Klagenfurt, Austria
[3] France Telecom, R&D, F-92794 Issy Les Moulineaux, France
来源：
MATHEMATICAL PROGRAMMING | 2003年 / 95卷 / 01期
关键词：
graph partitioning; semidefinite programming;
D O I：
10.1007/s10107-002-0342-x
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France Telecom networks with up 900 nodes, and also on randomly generated problems.
引用
收藏
页码：91 / 101
页数：11
相关论文
共 15 条
[1]  
BATTITI R, 1999, IEEE T COMPUTERS, V48
[2]   THE EQUIPARTITION POLYTOPE .2. VALID INEQUALITIES AND FACETS [J].
CONFORTI, M ;
RAO, MR ;
SASSANO, A .
MATHEMATICAL PROGRAMMING, 1990, 49 (01) :71-90
[3]   THE EQUIPARTITION POLYTOPE .1. FORMULATIONS, DIMENSION AND BASIC FACETS [J].
CONFORTI, M ;
RAO, MR ;
SASSANO, A .
MATHEMATICAL PROGRAMMING, 1990, 49 (01) :49-70
[4]  
Diekmann R., 1995, Interconnection Networks and Mapping and Scheduling Parallel Computations. DIMACS Workshop, P57
[5]   LOWER BOUNDS FOR PARTITIONING OF GRAPHS [J].
DONATH, WE ;
HOFFMAN, AJ .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1973, 17 (05) :420-425
[6]   Formulations and valid inequalities for the node capacitated graph partitioning problem [J].
Ferreira, CE ;
Martin, A ;
deSouza, CC ;
Weismantel, R ;
Wolsey, LA .
MATHEMATICAL PROGRAMMING, 1996, 74 (03) :247-266
[7]   The node capacitated graph partitioning problem: A computational study [J].
Ferreira, CE ;
Martin, A ;
de Souza, C ;
Weismantel, R ;
Wolsey, LA .
MATHEMATICAL PROGRAMMING, 1998, 81 (02) :229-256
[8]  
Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[9]  
Horn R. A., 1986, Matrix analysis
[10]  
Karisch SE, 1998, TOPICS SEMIDEFINITE, V18, P77
12