Patent ID: 7860012

Claim:
A method executed in a computer for identifying a least-cost path between a node A of a network (node Nl 1 ) of nodes that are interconnected by links and a node B (node Nr 2 ) the network, where associated with each link is a cost measure for traversing the link, comprising the steps of: dividing the network into a chosen number M≧3 segments, where a first one of the segments contains said node A, some of said nodes, some of said links, and a first plurality of half nodes formed from some of said nodes (half nodes Nr 1 ), a second one of the segments contains node B, some of said nodes, some of said links, and a second plurality of half nodes formed from some of said nodes(half nodes Nl 2 ), and remainder of said M segments between said segment and said second segment, each one of said segments in said remainder segments having a plurality of half nodes Nl i and a plurality of half nodes Nr i , and some of said nodes and some of said links interposed between the half nodes, where index 3≦i≦M designates the segments; in connection with each of the M segments, executing, substantially concurrently, an associated algorithm to compute least-cost intra-segment path costs, where an intra-segment path extends from a left node Nl i of said segment to a right node Nl k of said segment and comprises links of only said segment, and an intra-segment path cost is a sum of the costs associated with the links of which the intra-segment path is comprised; identifying said least-cost path between said node A and said node B using results of the substantially concurrent executions of the algorithms associated with said segments; and employing said least-cost path for establishing communication between said node A and said node B; where each left half segment in a segment belongs to a node that has a half node in another segment, and said dividing selects a portion of said network for each of said segments to include a number nodes and a number of links that result in approximately the same processing time for said segments.