DocumentCode
1969855
Title
New lower bounds for single row routing problems
Author
Sherwani, Naveed A. ; Deogun, Jitender S.
Author_Institution
Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA
fYear
1989
fDate
14-16 Aug 1989
Firstpage
535
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
Keywords
circuit layout; computational complexity; graph theory; network topology; NP-complete; VLSI layout; computational effort; containment graph; graph-theoretic representation; interval graph; lower bounds; overlap graph; routeing; single row routing problems; Algorithm design and analysis; Computational Intelligence Society; Computer science; Genetic mutations; Integrated circuit interconnections; Nonhomogeneous media; Printed circuits; Routing;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1989., Proceedings of the 32nd Midwest Symposium on
Conference_Location
Champaign, IL
Type
conf
DOI
10.1109/MWSCAS.1989.101909
Filename
101909
Link To Document