A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs |
| |
| Institution: | 1. College of Business and Economics, Qatar University, Doha, Qatar;2. The Bucharest University of Economic Studies, Bucharest, Romania;1. Department of Economics, Universidad Pablo de Olavide, Spain;2. Department of Statistics and Operations ResearchUniversidade de Vigo, Spain;1. Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Hans-Meerwein-Str. 6, 35032, Marburg, Germany;2. Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Ernst-Reuter-Platz 7, 10587, Berlin, Germany |
| |
| Abstract: | 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 diagraphs. 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
