Description: Abstract: Finding networks with minimal cost to connect points is a key problem in VLSI design, which can be
described as obstacle-avoiding shortest path and minimum Steiner tree problem according to whether the number of
points is greater than 2. Connection graphs, such as track based on graphs GC and GT and free area based graphs
GF and GG, are effective tools for the shortest path problem, which is the foundation of the Steiner tree problem.
The contribution of this paper includes three points: The dynamic algorithms for querying the shortest path between
two points on each connection graph are designed and analyzed for the first time secondly, all algorithms for
Steiner problem on each connection graph are analyzed The number of candidate Steiner points is reduced from
O((e+p)
2
) to O((t+p)
2
) in the 3-Steiner algorithm on GC, where e, t, p presents the number of edges, extreme edges
of obstacles and terminals An average Θ(t) algorithm for
To Search:
File list (Check if you may need any files):
On Optimal Rectilinear Shortest Paths and 3-Steiner Tree Routing in Presence of Obstacles.PDF
Download