GENETIC ALGORITHMS FOR DRAWING BIPARTITE GRAPHS

被引：8

作者：

MAKINEN, E

SIERANTA, M

机构：

[1] University of Tampere, Department of Computer Science, Tampere, FIN-33101

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1994年 / 53卷 / 3-4期

关键词：

BIPARTITE GRAPH; GRAPH DRAWING; GENETIC ALGORITHM;

D O I：

10.1080/00207169408804322

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper introduces genetic algorithms for the level permutation problem (LPP). The problem is to minimize the number of edge crossings in a bipartite graph when the order of vertices in one of the two vertex subsets is fixed. We show that genetic algorithms outperform the previously known heuristics especially when applied to low density graphs. Values for various parameters of genetic LPP algorithms are tested.

引用

页码：157 / 166

页数：10

共 16 条

[1]

BIENSTOCK D, 1990, 8TH P ANN ACM S COMP, P253

[2]

DIBATTISTA G, 1993, UNPUB ALGORITHMS GRA

[3] EDGE CROSSINGS IN DRAWINGS OF BIPARTITE GRAPHS [J].

EADES, P ;

WORMALD, NC .

ALGORITHMICA, 1994, 11 (04) :379-403

[4]

EADES P, 1985, 60 U QUEENSL DEPT CO

[5]

EADES P, 1989, 108 U QUEENSL DEPT C

[6]

EADES P, 1986, ARS COMBINATORIA A, V21, P89

[7]

Eades P., 1986, 69 U QUEENSL DEP COM

[8] CROSSING NUMBER IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (03) :312-316

[9]

Koebe M., 1990, J INF PROCESS CYBERN, V26, P377

[10] EXPERIMENTS ON DRAWING 2-LEVEL HIERARCHICAL GRAPHS [J].

MAKINEN, E .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1990, 36 (3-4) :175-181

← 1 2 →