GRASP and path relinking for 2-layer straight line crossing minimization

GRASP and path relinking for 2-layer straight line crossing minimization

0.00 Avg rating0 Votes
Article ID: iaor20001030
Country: United States
Volume: 11
Issue: 1
Start Page Number: 44
End Page Number: 52
Publication Date: Dec 1999
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: graphs
Abstract:

In this article, we develop a greedy randomized adaptive search procedure for the problem of minimizing straight line crossings in a 2-layer graph. The procedure is fast and is particularly appealing when dealing with low-density graphs. When a modest increase in computational time is allowed, the procedure may be coupled with a path relinking strategy to search for improved outcomes. Although the principles of path relinking have appeared in the tabu search literature, this search strategy has not been fully implemented and tested. We perform extensive computational experiments with more than 3,000 graph instances to first study the effect of changes in critical search parameters and then to compare the efficiency of alternative solution procedures. Our results indicate that graph density is a major influential factor on the performance of a solution procedure.

Reviews

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