Combining Breadth-First with Depth-First Search Algorithms for VLSI Wire Routing

摘要：

A breadth-first search (BFS) algorithm usually needs less time but consumes more computer memory space than a depth-first search (DFS) algorithm to find the shortest path between two nodes. This paper attempts to combine BFS with DFS algorithms to find all shortest paths in the VLSI (Very Large Integration Circuits) wire routing. BFS is used to compute the shortest distance between every position and the start one. DFS is used to traverse all shortest paths in the course of backtracking from the end position to the start one. The effectiveness of the method is proved by the theoretical analysis and the experiment results.

关键词： breadth-first serach depth-first serach wire routing shortest paths

作者: Xinguo Deng Yangguang Yao Jia Chen Yufeng Lin

作者单位: Center for Discrete Mathematics and Software College,Fuzhou UniversityCDM & SW, FZUFuzhou, China Software College,Fuzhou UniversitySW, FZUFuzhou, China Software College, Fuzhou University SW, FZU Fuzhou, China

会议类型: 国际会议

会议名称: 2010 3rd International Conference on Advanced Computer Theory and Engineering(2010年第三届先进计算机理论与工程国际会议 ICACTE 2010)

会议地点: 成都

会议语种:英文

页码: 1-5

在线出版日期: 2010-08-20（万方平台首次上网日期，不代表论文的发表时间）