\begin{slide}{Constraint-Graphen für IDL}

Für gegebenes IDL-System $S$ konstruiere 
gerichteten kantenbewerteten Graphen $G$
  \begin{itemize}
  \item Knoten $i$ $=$ Unbekannte $t_i$
  \item gewichtete Kante $i \stackrel{d}{\to} j$, 
    falls Constraint $t_i + d \ge t_j$
  \end{itemize}
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.

\end{slide}

