Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1985
Published Date
1985
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online