Constraint condition evaluation method and constraint condition

Details Constraint condition evaluation method and constraint condition Constraint condition evaluation method and constraint condition

1996-06-14

1999-10-26

Teska, Kevin J.

Boots, shoes, and leggings

364488, 364490, 364491, G06F 1700, G06F 1750

Patent

active

059715960

ABSTRACT:
It is an object of this invention is to provide a constraint condition evaluation method and a constraint condition evaluation system which detect PCs speedily in a constraint graph in a large system. To achieve this object, the system has the disassembling means (3) which disassembles a constraint graph, representing the constraints in the layout of components, into a plurality of subgraphs according to a specific division method while retaining the cycles in the constraint graph, the back edge detecting means (4) which detects back edges in each subgraph, and the PC detecting means (5) which detects PCs associated with the back edge in each subgraph. The system disassembles a constraint graph into smaller subgraphs to prevent the processing time increase rate from increasing, and reduces the PC detection time.

REFERENCES:
patent: 5450535 (1995-09-01), North
patent: 5452238 (1995-09-01), Kramer et al.
patent: 5568396 (1996-10-01), Bamji et al.
patent: 5581474 (1996-12-01), Bamji et al.
James Do et al., "Spacer II: A Well-Behaved IC Layout Compactor," IFIP, pp. 282-291 (1986).
Y. Eric Cho, "A Subjective Review of Compaction," IEEE, pp. 396-404 (1985).
Yuh-Zen Lioa et al., "An Algorithim to Compact a VLSI Symbolic Layout with Mixed constraints," IEEE, pp. 62-62-69 (1983).
A.V. Aho et al., "Data Structure and Algorithim," Baifukan Publishing Co., p. 195, Sec. 6 & 7. No date.
Masao Iri, et al., "Graph Theory Exercise", Corona Publishing Co., p. 4. No date.
Kiyoshi Ishihata, "Algorithm and Data Structure", Iwanami Software Science Series, pp. 242-244. No date.
Reference 4--no translation--A larger set of vertexes in a directed graph, in which paths exist from every vertex to all others, is called strongly-connected component in the directed graph, p. 195, section 6.7, first paragraph, lines 2-3. No date.
Reference 5--no translation--The removal of an edge k.epsilon.E from the graph G=(V, E), with the both ends remaining in the graph, is called removal processing (deletion) of edge k, and this makes a partial graph G'=(V, E-{l}), p. 4, lines 12-14. No date.
Reference 7--no translation--Such an order relationship in which two elements may be incomparable with each other, is called partial order (partial order). If a.sub.i <a.sub.j and a.sub.j <a.sub.k, then a.sub.i <a.sub.k is valid (transitive rule). The problem is how to charge the order of a plurality of given data so as to be consistent with a predetermined partial order. This is called topological sort (topological sort), p. 242, fourth line from the bottom to p. 243, line 2. No date.
K. Ishima et al., "On an Algorithm to Detect Positive Cycles in a Constraint Graph for Layout Compaction", IEICE Transactions, E 74(11):3613-3616 (1991).

Affiliated with

Also associated with

Rating

Constraint condition evaluation method and constraint condition does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Constraint condition evaluation method and constraint condition , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint condition evaluation method and constraint condition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-756108