DocumentCode
1454978
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
Volume
47
Issue
11
fYear
1998
fDate
11/1/1998 12:00:00 AM
Firstpage
1310
Lastpage
1312
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;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.736445
Filename
736445
Link To Document