GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
- 1 February 1999
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 11 (1), 44-52
- https://doi.org/10.1287/ijoc.11.1.44
Abstract
In this article, we develop a greedy randomized adaptive search procedure (GRASP) 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.Keywords
This publication has 15 references indexed in Scilit:
- A tabu search algorithm for the bipartite drawing problemEuropean Journal of Operational Research, 1998
- Arc crossing minimization in hierarchical digraphs with tabu searchComputers & Operations Research, 1997
- A GRASP for graph planarizationNetworks, 1997
- Tabu SearchPublished by Springer Science and Business Media LLC ,1997
- 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic AlgorithmsJournal of Graph Algorithms and Applications, 1997
- The assignment heuristic for crossing reductionIEEE Transactions on Systems, Man, and Cybernetics, 1995
- A technique for drawing directed graphsIEEE Transactions on Software Engineering, 1993
- Experiments on drawing 2-level hierarchical graphsInternational Journal of Computer Mathematics, 1990
- A probabilistic heuristic for a computationally difficult set covering problemOperations Research Letters, 1989
- Automatic Display of Hierarchized Graphs for Computer-Aided Decision AnalysisIEEE Transactions on Systems, Man, and Cybernetics, 1980