Paper Info
Title
A Prim-based Heuristic Algorithm for Obstacle Avoiding Rectilinear Steiner Minimal Tree
Abstract
Obstacle Avoiding Rectilinear Steiner Minimal Tree (OARSMT) is known to provide the shortest interconnection between n terminals in the presence of m obstacles using the rectilinear distance. We introduce a new line-based graph, which we call the Maneuver Graph that constructs a reduced set of possible paths between any two terminals in the presence of m obstacles with complexity of O(m). Moreover, a dynamic programming algorithm is developed to recover the two-terminal shortest path over the Maneuver Graph with complexity of O(m). Based on the Maneuver Graph we introduce a Prim-based heuristic algorithm that constructs an approximated OARMST in a way analogous to the Obstacle Avoiding Rectilinear Minimum Spanning Tree (OARMST) construction. The nearest terminal is redefined as that one with the shortest interconnection to a terminal, a Steiner or a corner point of the currently constructed sub-tree. This interconnection is established with minimum added tree length and maximum overlap with the already existing interconnections. We show that this algorithm has at worst a complexity of O(n3m2), which is still less than those of 4-steinerization methods. We also show that the algorithm can achieve a percentage-of-improvement about 10% over OARMST which is better than that obtained by the k-steinerization methods.
Year
DOI
Venue
2001
10.1016/S1571-0653(05)80092-7
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Steiner Tree,Minimum Spanning Tree,Dynamic Programming,Prim Heuristic and Heuristic Algorithms
Discrete mathematics,Combinatorics,Distributed minimum spanning tree,Shortest path problem,Prim's algorithm,Steiner tree problem,Spanning tree,Shortest-path tree,Mathematics,Kruskal's algorithm,Minimum spanning tree
Journal
Volume
ISSN
Citations 
8
1571-0653
0
PageRank 
References 
Authors
0.34
1
2
Name
Order
Citations
PageRank
M.M.Ibrahim Mohamed100.34
B. Tawfik200.68