Eine Greedy-Heuristik für die Lösung des Cograph Editing Problems

Authors: 
Hainke, Kai-Adrian
Year: 
2015
Language: 
German
Abstract: 
Diese Arbeit betrachtet das Cograph Editing Problem im Kontext der Rekonstruktion phylogenetischer Bäume. Insbesondere muss dafür ein Cograph rekonstruiert werden, der durch Rauschen verzerrt wurde. Liu et al. zeigten, dass Cograph Editing NP-vollständig ist. Damit ist das Problem für große Graphen wahrscheinlich nicht in realistischer Zeit korrekt lösbar. Diese Arbeit stellt daher eine Greedy-Heuristik für die Lösung des Cograph Editing Problems vor. Dabei werden Editieroperationen als günstig betrachtet, wenn sie die Anzahl an induzierten P4 in dem Graphen minimieren. Es wird ein on-line Algorithmus zur Berechnung dieser Heuristik vorgestellt und analysiert. Anschließend wird ein Greedy-Algorithmus formuliert, der eine heuristische Lösung des Cograph Editing Problems in O(|V|^4) Zeit und unter Nutzung von O(|V|^2) Speicher berechnet. Eine Implementierung dieses Greedy-Algorithmus wird auf zufällig generierten Testdaten untersucht. Parallel dazu wird auch eine Implementierung für die korrekte Lösung des Cograph Editing Problems getestet. Dabei werden die Qualität der Ergebnisse und die Laufzeit gemessen und verglichen. Hier zeigte sich, dass der Greedy-Algorithmus bei der Rekonstruktion von durch Rauschen verzerrter Cographen vergleichbar gute Ergebnisse erzielen konnte.
AttachmentSize
bachelorarbeit.pdf792.01 KB