109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-011-06-0916 28418 Research Article B.7.2 - Design Aids F.2.2 - Nonnumerical Algorithms and Problems On Theoretical Upper Bound for Routing Estimation He Fei hef02@mails.tsinghua.edu.cn 1 Cheng Lerong 2 Yang Guowu 2 Song Xiaoyu 2 Gu Ming 3 Sun Jiaguang 3 Dept. CS&T and School of Software, Tsinghua University, , China Dept. CS&T and School of Software, Tsinghua University China Dept. ECE, Portland State University, , United States of America Dept. ECE, Portland State University United States of America School of Software, Tsinghua University, , China School of Software, Tsinghua University China

Corresponding author: Fei He (hef02@mails.tsinghua.edu.cn).

Academic editor:

2005 28 06 2005 11 6 916 925 20DC49A0-D711-5A7B-A6CC-3C7DE81B0EC4 6996777 Fei He, Lerong Cheng, Guowu Yang, Xiaoyu Song, Ming Gu, Jiaguang Sun This article is freely available under the J.UCS Open Content License.

Routing space estimation plays a crucial role in design automation of digital systems. We investigate the problem of estimating upper bounds for global routing of two-terminal nets in two-dimensional arrays. We show the soundness of the bounds for both wiring space and total wire-length estimation.