Exakte Algorithmen für NP-harte Probleme auf Netzwerken

dc.contributor.author	Alber, Jochen
dc.contributor.editor	Wagner, Dorothea
dc.date.accessioned	2017-09-22T20:42:06Z
dc.date.available	2017-09-22T20:42:06Z
dc.date.issued	2004
dc.description.abstract	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.	de
dc.identifier.isbn	978-3-88579-408-X
dc.identifier.pissn	1617-5468
dc.identifier.uri	https://dl.gi.de/handle/20.500.12116/4485
dc.language.iso	de
dc.publisher	Gesellschaft für Informatik
dc.relation.ispartof	Ausgezeichnete Informatikdissertationen 2003
dc.relation.ispartofseries	Lecture Notes in Informatics (LNI) - Dissertations, Volume D-4
dc.title	Exakte Algorithmen für NP-harte Probleme auf Netzwerken	de
gi.citation.endPage	28
gi.citation.publisherPlace	Bonn
gi.citation.startPage	19

Dateien

1 - 1 von 1