A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

0.00 Avg rating0 Votes
Article ID: iaor19971498
Country: Netherlands
Volume: 63
Issue: 1
Start Page Number: 233
End Page Number: 251
Publication Date: May 1996
Journal: Annals of Operations Research
Authors: , ,
Keywords: heuristics
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, the authors 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. The present algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test problems, size permitting.

Reviews

Required fields are marked *. Your email address will not be published.