Constraint-Graphen für IDL

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

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

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

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

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