Method of computation of a short path in valued graphs

Details Method of computation of a short path in valued graphs Method of computation of a short path in valued graphs

2008-07-29

2008-07-29

Ngo, Ricky (Department: 2616)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C709S241000

Reexamination Certificate

active

10849754

ABSTRACT:
A method of computing shortest paths in a weighted graph having vertices and an adjacency matrix with memory resources and a processor including (a) selecting integer weights; (b) carrying out a series of incrementations, an incrementation including finding a set of vertices to which one may arrive from a given set of vertices; (c) carrying out a series of decrementations, a decrementation including finding a set of vertices from which one may go to arrive to a given set of vertices; (d) causing the incrementations and decrementations to be carried out in any order; (e) transforming vectors of increments/decrements in paths, the paths making up a set E1of the shortest paths in term of number of arcs or using a given number of arcs, Na; (f) selecting n-uple of paths C of lowest cost among set of paths E1; (g) calculating Nb=Na+1; (h) computing iteratively, while Nb≦W(C) the following steps: i. check among paths of length Na+1 if in existence, having a weight lower than W(C) and selecting among them C′ of lowest cost (if such a path does not exist, then C′=C); and ii. C=C′ and Nb=Nb+1; and (i) determining paths of lowest weight based on C.

REFERENCES:
patent: 6356911 (2002-03-01), Shibuya
patent: 6477515 (2002-11-01), Boroujerdi et al.
patent: 6665852 (2003-12-01), Xing et al.
patent: 2002/0107711 (2002-08-01), Xing et al.

Affiliated with

Also associated with

Rating

Method of computation of a short path in valued graphs 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 computation of a short path in valued graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of computation of a short path in valued graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3924364