Datenreduktion und Problemkerne

ISBN-13: 9783656438120 / Niemiecki / Miękka / 2016 / 28 str.

Sebastian Schaf; Albert Bub

Opis

Studienarbeit aus dem Jahr 2013 im Fachbereich Informatik - Theoretische Informatik, Universitat Ulm, Veranstaltung: Algorithmen und Datenstrukturen, Sprache: Deutsch, Abstract: Diese Ausarbeitung beschaftigt sich mit der Reduktion von Problemen auf einen Problemkern in Graphen. Es wird erlautert was ein Kern und was eine Reduktionsregel ist. Es werden verschiedene Reduktionsregeln vorgestellt um ein gegebenes Problem zu reduzieren. Anhand des Vertex Covers wird beispielhaft die Anwendung dieser Reduktionsregeln demonstriert. Mit dem Hitting-Set-Problem erweitert sich dann anschlieend das Feld der Reduktionsmoglichkeiten auf die Hypergraphen - dabei wird auch gezeigt, warum es so schwer ist, eine optimale Minimierung zu finden. Das letzte Kapitel dagegen widmet sich den Reduktionsmoglichen mit Hilfe des Dominating-Sets. Hierbei handelt sich jedoch wieder um eine Reduktionsmoglichkeit von normalen Graphen.