Abstract
New lower bounds for single-row routing problems are presented. The new lower bounds are based on a graph-theoretic representation in which an instance of the single-row routing problem is represented by three graphs, an overlap graph, a containment graph, and an interval graph. These bounds improve the best known existing bounds. Lower bounds are important for saving computational effort in routing since the single-row routing problem is NP-Complete.
| Original language | English (US) |
|---|---|
| Pages | 535-538 |
| Number of pages | 4 |
| State | Published - 1990 |
| Externally published | Yes |
| Event | Proceedings of the 32nd Midwest Symposium on Circuits and Systems Part 2 (of 2) - Champaign, IL, USA Duration: Aug 14 1989 → Aug 16 1989 |
Other
| Other | Proceedings of the 32nd Midwest Symposium on Circuits and Systems Part 2 (of 2) |
|---|---|
| City | Champaign, IL, USA |
| Period | 8/14/89 → 8/16/89 |
ASJC Scopus subject areas
- Electronic, Optical and Magnetic Materials
- Electrical and Electronic Engineering