Constraint-Graphen für IDL

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

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.

2014-07-06