Constraint-Graphen für IDL

Für gegebenes IDL-System S konstruiere gerichteten kantenbewerteten Graphen G

• Knoten i = Unbekannte t_i
• gewichtete Kante i$\;\stackrel{{d}}{{\to}}\;$j, falls Constraint t_i + d$\ge$t_j

beachte: Gewichte d können negativ sein. (wenn nicht: Problem ist trivial lösbar)

Satz: S lösbar $\iff$ G besitzt keinen gerichteten Kreis mit negativem Gewicht.

Implementierung: Information über Existenz eines solchen Kreises fällt bei einem anderen Algorithmus mit ab.