ISSN:
1572-9338
Keywords:
Tabu thresholding
;
tabu search
;
arc crossing minimization
;
automatic graph drawing
;
heuristics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test problems, size permitting.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02125456
Permalink