Sq. Zheng et al., FINDING OBSTACLE-AVOIDING SHORTEST PATHS USING IMPLICIT CONNECTION GRAPHS, IEEE transactions on computer-aided design of integrated circuits and systems, 15(1), 1996, pp. 103-110
We introduce a framework for a class of algorithms solving shortest pa
th related problems, such as the one-to-one shortest path problem, the
one-to-many shortest paths problem and the minimum spanning tree prob
lem, in the presence of obstacles. For these algorithms, the search sp
ace is restricted to a sparse strong connection graph that is implicit
ly represented and its searched portion is constructed incrementally o
n-the-fly during search. The time and space requirements of these algo
rithms essentially depend on actual search behavior. Therefore, additi
onal techniques or heuristics can be incorporated into search procedur
e to further improve the performance of the algorithms. These algorith
ms are suitable for large VLSI design applications with many obstacles
.