Item Details

Heuristics for Backplane Ordering

Cohoon, James; Sahni, Sartaj
Format
Report
Author
Cohoon, James
Sahni, Sartaj
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1985
Published Date
1985
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online