Title :
A simple approximation algorithm for two problems in circuit design
Author :
Carpenter, Tamra ; Cosares, Steven ; Ganley, Joseph L. ; Saniee, Iraj
Author_Institution :
Bellcore, Morristown, NJ, USA
fDate :
11/1/1998 12:00:00 AM
Abstract :
This paper provides a very simple two-approximation algorithm for two NP-hard problems that arise in electronic circuit design. To our knowledge, this is the best approximation bound known for these problems. In addition, the simplicity of the proposed algorithm makes it attractive for real-time applications for similar problems in areas such as telecommunications and parallel processing
Keywords :
circuit CAD; computational complexity; graph theory; NP-hard problems; approximation algorithms; approximation bound; electronic circuit design; graph embedding; moat routing; two-approximation algorithm; Algorithm design and analysis; Approximation algorithms; Circuit synthesis; Clocks; Electronic circuits; NP-hard problem; Parallel processing; Routing; Telecommunication congestion control; Wires;
Journal_Title :
Computers, IEEE Transactions on
