Abstract—In VLSI design, one of the most important detailed routings is the channel routing. Given a channel with length n in 2-layer Manhattan model, Szeszler proved that the width (number of tracks required for routing) of the channel is at most 7/4n, and this upper bound can be achieved by a linear time algorithm. In this note, we improve the upper bound 7/4n to 3/2n, which also can be achieved by a linear time algorithm.
Keywords—Channel routing, Graph Theory, VLSI design.
AD Publications is a rapidly growing academic publisher in the fields of Engineering, Medical-Health, Environmental Science and Agriculture Research. AD Publications is a registered organization broad-based open access and publishes most exciting researches with respect to the subjects of our journals. The Journals is being indexed and abstracted by all major global current awareness and alerting services.
The organization aims at undertaking, co- coordinating and promoting research and development. It provides professional and academic guidance in the field of basic education, Higher Education as well in the Technical Education. Our Aims is to Promote and support, High Quality basic, Scientific Research and development in fields of Engineering, Medical-Health, Environmental Science and Agriculture Research and to Generate Public awareness, provide advice to scholar’s researchers and communicate research outcomes.