Method of accelerating the shortest path problem

Details Method of accelerating the shortest path problem Method of accelerating the shortest path problem

2007-02-02

2010-02-16

Pham, Brenda (Department: 2416)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S383000

Reexamination Certificate

active

07664040

ABSTRACT:
The solution to the shortest path between a source node and multiple destination nodes is accelerated using a grouping of nodes, where the nodes are grouped based on distance from the source node, and a corresponding set of memory locations that indicate when a group includes one or more nodes. The memory locations can be quickly searched to determine the group that represents the shortest distance from the source node and that includes one or more nodes. Nodes may be grouped into additional groupings that do not correspond to the set of memory locations, when the distance from the source node to the nodes exceeds the range of memory locations. Advantageously, the disclosed system and method provide the ability to reach asymptotically optimal performance.

REFERENCES:
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6034946 (2000-03-01), Roginsky et al.
patent: 6289096 (2001-09-01), Suzuki
patent: 6356911 (2002-03-01), Shibuya
patent: 6370119 (2002-04-01), Basso et al.
patent: 6529498 (2003-03-01), Cheng
patent: 6532212 (2003-03-01), Soloway et al.
patent: 7047317 (2006-05-01), Huie et al.
patent: 7457286 (2008-11-01), Alexander, Jr.
patent: 2002/0054572 (2002-05-01), Saleh et al.
“Single Source Shortest Path (SSSP) Problem”, http://www.cs.rochester.edu/users/faculty
elson/courses/csc—173/graphs/sssp.html, downloaded Mar. 16, 2003, 3 pages.

Affiliated with

Also associated with

Rating

Method of accelerating the shortest path problem does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of accelerating the shortest path problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of accelerating the shortest path problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4180929