\begin{slide}{Registervergabe}

  \begin{itemize}
  \item 
Werte von lokalen Variablen in Blöcken
und von (Teil-)Ausdrücken sollten, wenn möglich,
in Prozessor-Registern stehen, 
(Zugriff ist sehr viel schneller aus auf Hauptspeicher).
\item
  gleichzeitig benötigte Werte müssen in verschiedenen Registern stehen
  (definiert Graph)
\item
  Registerzahl der CPU ist begrenzt (Anzahl der Farben)
\end{itemize}

Problem COL$=\{(G,k):$ Graph $G$ besitzt konfliktfreie Färbung
mit $k$ Farben $\}$.

\dots 3COL ist NP-vollständig (Reduktion von 3SAT)

\end{slide}

\begin{slide}{3COL -- Hausaufgabe} 

finde einen Baustein $H$ mit den Eigenschaften:
\begin{itemize}
\item von $H$ führen genau 4 Kanten nach außen
\item wenn die dadurch bestimmten 4 Nachbarknoten von $H$
  alle identisch gefärbt sind, läßt sich das nicht
  zu einer 3-Färbung von $H$ fortsetzen.
\item
  wenn die 4 Nachbarknoten insgesamt genau zwei Farben benutzen,
  dann läßt sich das zu einer 3-Färbung von $G$ fortsetzen.
\end{itemize}

\end{slide}

\begin{slide}{Färbung (Heuristik)}

Farben $\{1,2,\ldots, k\}$
  \begin{itemize}
  \item 
nächster freier Knoten
erhält kleinste freie Farbe
\item
  Knotenreihenfolge wählen z. B. nach Grad (im Restgraphen)
  \end{itemize}
wie gut ist diese Heuristik?



\end{slide}
