Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Exponentialzeit-Algorithmen für Färbbarkeitsprobleme
verfasst von : Priv.-Doz. Dr. Frank Gurski, Prof. Dr. Irene Rothe, Prof. Dr. Jörg Rothe, Prof. Dr. Egon Wanke
Erschienen in: Exakte Algorithmen für schwere Graphenprobleme
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Zunächst stellen wir in diesem Abschnitt ein paar Algorithmen vor, die auf einfachen Ideen beruhen und den naiven Algorithmus für Dreifärbbarkeit bereits schlagen (auch wenn sie natürlich immer noch Exponentialzeit brauchen; schließlich ist das Dreifärbbarkeitsproblem nach Satz 5.26 NP-vollständig). Anschließend gehen wir kurz auf die Motivation für exakte Exponentialzeit-Algorithmen ein und erläutern, weshalb solche Verbesserungen für praktische Anwendungen sehr sinnvoll sein können.