|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 13 van 30 gevonden artikelen
| Titel: |
Arc crossing minimization in graphs with GRASP |
| Auteur: |
Marti, Rafael |
| Verschenen in: |
IIE transactions |
| Paginering: | Jaargang 33 (2001) nr. 10 pagina's 913-919 |
| Jaar: |
2001-10-01 |
| Inhoud: |
Graphs are commonly used to represent information in many fields of science and engineering. Automatic drawing tools generate comprehensible graphs from data, taking into account a variety of properties, enabling users to see important relationships in the data. The goal of limiting the number of arc crossings is a well-admitted criterion for a good drawing. In this paper, we present a Greedy Randomized Adaptive Search Procedure (GRASP) for the problem of minimizing are crossings in graphs. Computational experiments with 200 graphs with up to 350 vertices are presented to assess the merit of the method. We show that simple heuristics are very fast but result in inferior solutions, while high-quality solutions have been found with complex meta-heuristics but demand an impractical amount of computer time. The proposed GRASP algorithm is better in speed than complex meta-heuristics and in quality than simple heuristics. Thus, it is a clear candidate for practical implementations in graph drawing software systems. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 13 van 30 gevonden artikelen
| << vorige | volgende >> |