Textdokument
Exakte Algorithmen für NP-harte Probleme auf Netzwerken
Lade...
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.