Aller au contenu. | Aller à la navigation

Outils personnels

Navigation
Vous êtes ici : Accueil / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Realistische Problemstellungen sind #tex2html_wrap_inline5312#-vollständig

Realistische Problemstellungen sind #tex2html_wrap_inline5312#-vollständig

next up previous contents
Next: Approximierbarkeit Up: Komplexität des Problems Previous: Polynomiell lösbare Fälle

Realistische Problemstellungen sind tex2html_wrap_inline5146 -vollständig

In [EIS76] wurde erstmals ein recht allgemeines Timetabling-Problem als tex2html_wrap_inline5146 -vollständig nachgewiesen. Dennoch ist dieser Beweis nicht vollständig zufriedenstellend, da das Konstrukt ein ausgesprochen unrealistisches Stundenplanproblem verwendet. Zahlreiche Reduktionen tex2html_wrap_inline5146 -vollständiger Probleme für verschiedene (einfache) Erweiterungen des STP finden sich in [CK95a] und [dWMP93], aber auch hier werden überwiegend unrealistische Fälle verwendet. Da die verwendeten Methoden - auch wegen der Art der Konstrukte - nicht instruktiv bezüglich eines möglichen Lösungsverfahrens erscheinen, wird an dieser Stelle auf eine umfassende Darstellung verzichtet. Die tex2html_wrap_inline5146 -Vollständigkeit des in dieser Arbeit untersuchten Problems geht zudem auch aus der im nächsten Kapitel beschriebenen Reduktion des Graphenfärbungsproblems hervor.



(c) Martin Loehnertz 1999