Logo des Repositoriums
 
Textdokument

Exakte Algorithmen für NP-harte Probleme auf Netzwerken

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2004

Autor:innen

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

Wir befassen uns in der Arbeit mit dem Entwurf von exakten Algorithmen für verschiedene NP-vollständige Optimierungsprobleme auf Graphen, wie beispielsweise Vertex Cover, Independent Set oder Dominating Set. Im Vordergrund der Arbeit stehen exakte Lösungsverfahren mit beweisbaren Laufzeitschranken. Wir verfolgen dabei den jüngst vorgeschlagenen Ansatz sogenannter “parametrisierter Algorithmen”. Dabei untersuchen wir sowohl von theoretischer, als auch von praktischer Seite unterschiedliche Methoden des Algorithmen-Designs: Datenreduktion, beschränkte Suchbäume, Separation von Graphen und das Konzept von Baumzerlegungen. Schließ- lich stellen wir ein Software-Paket vor, welches im Rahmen dieses Projektes entwickelt wurde und eine Vielzahl der entwickelten Algorithmen implementiert.

Beschreibung

Alber, Jochen (2004): Exakte Algorithmen für NP-harte Probleme auf Netzwerken. Ausgezeichnete Informatikdissertationen 2003. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-408-X. pp. 19-28

Schlagwörter

Zitierform

DOI

Tags