Sign in
Back
A simple approximation algorithm for two problems in circuit design
Journal article   Peer reviewed

A simple approximation algorithm for two problems in circuit design

T Carpenter, S Cosares, J.L Ganley and I Saniee
IEEE transactions on computers, Vol.47(11), pp.1310-1312
11/1998
DOI: https://doi.org/10.1109/12.736445

Abstract

Algorithm design and analysis Approximation algorithms Circuit synthesis Clocks Electronic circuits NP-hard problem Parallel processing Routing Telecommunication congestion control Wires
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.

Metrics

9 Record Views
7 Times Cited - Web of Science

Details