Jünger, Michael and Mutzel, Petra (1996) Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization. [Conference Paper]
This is the latest version of this eprint.
Full text not available from this repository.
Abstract
We present algorithms for the two layer straightline crossing minimization problem that are able to compute exact optima.Our computational results lead us to the conclusion that there is no need for heuristics if one layer is fixed, even though the problem is NP-hard, and that for the general problem with two variable layers, true optima can be computed for sparse instances in which the smaller layer contains up to 15 nodes. For bigger instances, the iterated barycenter method turns out to be the method of choice among several popular heuristics whose performance we could assess by comparing the results to optimum solution.
| Item Type: | Conference Paper |
|---|---|
| Classifications: | G Algorithms and Complexity > G.700 Layering G Algorithms and Complexity > G.420 Crossings |
| ID Code: | 162 |
| Deposited By: | Maciejak, Agnes |
| Deposited On: | 19 Apr 2005 |
| Last Modified: | 18 Sep 2008 13:08 |
Available Versions of this Item
- Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization. (deposited 17 Jul 2003)
- Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization. (deposited 19 Apr 2005) [Currently Displayed]
Repository Staff Only: item control page
