Heuristics for Backplane OrderingReport
The Board Permutation Problem, a backplane ordering problem, has been previously shown to be NP - hard. We develop here several heuristics for the Board Permutation Problem. These heuristics produce solutions that are locally optimal with respect to some nontrivial transforms. The heuristics are analytically shown to be m/3- approximate, where m is the number of nets in a problem instance. The heuristics have been shown experimentally to have quite acceptable behavior. Several of the heuristics make use of a Statistical Mechanics technique (simulated annealing) for thermal equilibrium analysis in producing their solution.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Cohoon, James, and Sartaj Sahni. "Heuristics for Backplane Ordering." University of Virginia Dept. of Computer Science Tech Report (1985).
University of Virginia, Department of Computer Science