Phylogenetische Bäume k-Blattpotenzen von Bäumen (k-leaf powers) und Varianten

• Applicant: Professor Dr. Andreas Brandstädt
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 30737035

Phylogenetische Bäume beschreiben Entwicklungsgeschichte bzw. Verwandtschaftsverhältnisse von Taxa (biologischen Arten, Sprachen bzw. anderen Objekten von Evolution). Ausgehend von (fehlerbehafteten) Daten zu Taxa soll der phylogenetische Baum T bestimmt werden, dessen innere Knoten Verzweigungsereignisse der Entwicklung darstellen, so daß die Taxa den Blättern von T zugeordnet sind. Viele Publikationen hierzu verwenden Graphenmodelle G = (V,E), V die Menge der Taxa, und für Taxa x, y E V ist xy E genau dann, wenn ihre Distanz im Baum T ¿klein genug¿ (¿ k) ist. T heißt dann (phylogenetische) Wurzel von G, und G ist Teilgraph der k-ten Potenz von T, eingeschränkt auf die Blätter von T. (Der Grad der inneren Knoten in T ist mindestens 3.) G ist dann chordaler Graph. Durch neue Charakterisierungen von Quadraten von Bäumen und weitere Strukturergebnisse haben wir wichtige Resultate von Nishimura, Ragde und Thilikos [48], von Rautenbach [49] sowie von Dom, Guo, Hüffner, Niedermeier [22, 23] verbessern können. Unser Ziel ist es, die Strukturtheorie der Baumpotenzen und der chordalen Graphen durch neue Potenzeigenschaften, Struktur dermaximalen Cliquen und minimalen Cliquenseparatoren zu einem systematischen und einheitlichen Zugang zu den oben genannten Modellen zu erweitern, um offene Probleme in diesem Gebiet zu lösen sowie bessere Algorithmen zu wichtigen Problemen wie z.B. der exakten und approximativen Bestimmung phylogenetischer Wurzeln zu erhalten.

• DFG Programme: Research Grants