A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs

被引：25

作者：

Valls, V ^{[1
]}

Marti, R ^{[1
]}

Lino, P ^{[1
]}

机构：

[1] UNIV VALENCIA,FAC CIENCIAS ECON & EMPRESARIALES,DEPT ECON FINANCIERA & MATEMAT,E-46010 VALENCIA,SPAIN

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1996年 / 90卷 / 02期

关键词：

branch and bound; crossing arcs minimization; automatic graph drawing; bipartite graphs;

D O I：

10.1016/0377-2217(95)00356-8

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Acyclic directed graphs are widely used in many fields of economic and social sciences. This has generated considerable interest in algorithms for drawing ''good'' maps of acyclic digraphs. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of crossing arcs. In this paper, we present a branch and bound algorithm for solving the problem of minimizing the number of crossing arcs in a bipartite graph. Computational results are reported on a set of randomly generated test problems.

引用

页码：303 / 319

页数：17

共 23 条

[1] CASE - AUTOMATIC-GENERATION OF ELECTRICAL DIAGRAMS [J].

AOUDJA, F ;

LABORIE, M ;

SAINTPAUL, A .

COMPUTER-AIDED DESIGN, 1986, 18 (07) :356-360

[2] A LAYOUT ALGORITHM FOR DATA FLOW DIAGRAMS [J].

BATINI, C ;

NARDELLI, E ;

TAMASSIA, R .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1986, 12 (04) :538-546

[3] AUTOMATIC DISPLAY OF HIERARCHIZED GRAPHS FOR COMPUTER-AIDED DECISION-ANALYSIS [J].

CARPANO, MJ .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1980, 10 (11) :705-715

[4]

CATARCI T, 1988, P 26 ANN ALL C

[5] HIERARCHIES AND PLANARITY THEORY [J].

DIBATTISTA, G ;

NARDELLI, E .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1988, 18 (06) :1035-1046

[6]

DIBATTISTA G, 1993, ALGORITHMS DRAWING G

[7]

EADES P, 1985, 60 U QUEENSL DEPT CO

[8]

EADES P, 1991, ALGORITHMICA 1206

[9]

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

[10]

JOHNSON DS, 1982, J ALGORITHM, V3, P97

← 1 2 3 →