Heuristics for Backplane Ordering

Report
Authors:Cohoon, James, Department of Computer ScienceUniversity of Virginia Sahni, Sartaj, Department of Computer ScienceUniversity of Virginia
Abstract:

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

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Cohoon, James, and Sartaj Sahni. "Heuristics for Backplane Ordering." University of Virginia Dept. of Computer Science Tech Report (1985).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1985
Persistent Link:
https://doi.org/10.18130/V37Z04