A simple approximation algorithm for two problems in circuit design

Tamra Carpenter

doi:10.1109/12.736445

A simple approximation algorithm for two problems in circuit design

1998-01-01

7

PRE

AI

DOI：10.1109/12.736445

Original

Original request for help

Save

Abstract

En 中文

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:

graph embedding

approximation algorithms

moat routing

A simple approximation algorithm for two problems in circuit design

Abstract

Journal

Organization