scientific article; zbMATH DE number 1538069

MaRDI QIDQ4518929zbMATH OpenFDO

Authors Rajat Kumar Pal

Publication date 3 December 2000

zbMATH Keywords

computational complexitydesign of algorithmsmulti-layer channel routing

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Analysis of algorithms and problem complexity (68Q25) Computer science aspects of computer-aided design (68U07)

Review text

[The book is also available from Chapman \& Hall/CRC, ISBN 0-8493-0931-X] The book ``Multi-Layer Channel Routing Complexity and Algorithms of Rajat K. Pal focuses on computational complexity and design of algorithms for multi-layer channel routing. Many theoretical results on NP-hardness of routing problems and bounds on optimal solutions targeting minimum chip area and wire length are presented. In particular, it gives an excellent survey on the algorithms presented in literature till 1990. Although channel routing algorithms are fundamental for the understanding for the development of advanced routing paradigms, the availability of multiple metal layers obviates the need of channel routing. Furthermore, Rajat K. Pal only focuses on routing area and wire length as optimization goals in channel routing. Other goals, as e.g. power consumption and signal delay, which depends not only on wire length, are not considered in this book.

Recommendations

• Algorithmic aspects of VLSI layout.
• Nearly optimal algorithms and bounds for multilayer channel routing
• scientific article; zbMATH DE number 4077133
• scientific article; zbMATH DE number 4037776
• VLSI physical design. From graph partitioning to timing closure

Cited in

(8)

• Channel routing in a diagonal overlap model
• Hexagonal three-layer channel routing
• Direct routing: Algorithms and complexity
• Packet Routing: Complexity and Algorithms
• scientific article; zbMATH DE number 3907789 (Why is no real title available?)
• scientific article; zbMATH DE number 4077133 (Why is no real title available?)
• scientific article; zbMATH DE number 3893100 (Why is no real title available?)
• Algorithms – ESA 2004

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4518929)