DocumentCode
3147700
Title
Heuristics for the Circuit Realization Problem
Author
Cohoon, James ; Sahni, Sartaj
Author_Institution
University of Minnesota
fYear
1983
fDate
27-29 June 1983
Firstpage
560
Lastpage
566
Abstract
The Circuit Realization Problem has been previously shown to be NP-hard. We develop here several heuristics for the Circuit Realization Problem. These heuristics are locally optimal with respect to a transform and are f(n)-approximation algorithms. Several of the heuristics make use of a Statistical Mechanics technique for thermal equilibrium analysis in producing their solution. In addition, the heuristics are experimentally shown to have quite acceptable behavior.
Keywords
Circuit realization; algorithms; approximations; complexity; design automation; local optimality; statistical mechanics; thermal equilibrium; Algorithm design and analysis; Application software; Chromium; Cost function; Design automation; Logic circuits; Polynomials; Printed circuits; Process design; Software tools; Circuit realization; algorithms; approximations; complexity; design automation; local optimality; statistical mechanics; thermal equilibrium;
fLanguage
English
Publisher
ieee
Conference_Titel
Design Automation, 1983. 20th Conference on
ISSN
0738-100X
Print_ISBN
0-8186-0026-8
Type
conf
DOI
10.1109/DAC.1983.1585709
Filename
1585709
Link To Document