Method for generating a preferred processing order and for detec

Details Method for generating a preferred processing order and for detec Method for generating a preferred processing order and for detec

1994-12-13

1997-05-27

Teska, Kevin J.

Boots, shoes, and leggings

364488, 364489, 364490, 364491, G06F 1700

Patent

active

056341130

ABSTRACT:
A method used by a digital computer for generating a preferred processing order of the vertices in a directed graph. The method also detects any cycles that exist in the directed graph. The vertices of the directed graph represent components of a system and the arcs represent the interrelationships between components. Each arc is defined by a vertex pair consisting of a starting vertex and an ending vertex. Each vertex is either assigned or unassigned to a processing order and marked as either a leaf vertex or a non-leaf vertex. The method includes traversing the set of arcs of the directed graph and marking the starting vertex as a non-leaf vertex for each arc whose ending vertex is unassigned, traversing the set of vertices and for each vertex that is unassigned and a leaf vertex, assigning the vertex to the processing order; and for each vertex that is unassigned and a non-leaf vertex, marking it as a leaf vertex. If unassigned vertices remain in the set of vertices and no vertices were assigned to the processing order then a cycle exists in the directed graph. These steps are repeated as long as there are vertices in the set of vertices that are unassigned and no cycle has been detected.

REFERENCES:
patent: 3579194 (1971-05-01), Weinblatt
patent: 4953106 (1990-08-01), Gansner et al.
patent: 5187785 (1993-02-01), Shah
patent: 5195172 (1993-03-01), Ehad et al.
patent: 5200888 (1993-04-01), Hashimoto
patent: 5201046 (1993-04-01), Goldberg et al.
patent: 5251290 (1993-10-01), Pabon
patent: 5394556 (1995-02-01), Oprescu
patent: 5450535 (1995-09-01), North
"Introduction to Algorithms" Cormen, Leiserson & Rivest Chapter 23, pp. 465-497, 1991 (Third Printing) QA76.6.C662.
Chachra, Vinod. "Applications of Graph Theory Algorithms", 1979, Elsevier North Holland, Inc., pp. 4-20.

Affiliated with

Also associated with

Rating

Method for generating a preferred processing order and for detec 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 for generating a preferred processing order and for detec, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating a preferred processing order and for detec will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2337300