|
Tina Janne Schmidt Mentor: Prof. Dr. Anusch Taraz
Stipendien und Auszeichnungen
Zurzeit beschäftige ich mich mit Algorithmen für möglichst große planare Subgraphen. Ein größter planarer Subgraph H eines Graphen G ist ein planarer Subgraph - also ein Teilgraph von G, der auf ein Blatt Papier gezeichnet werden kann ohne dass sich Kanten überkreuzen -, sodass es keinen Teilgraphen H' von G gibt, der planar ist und mehr Kanten als H hat. Größte planare Subgraphen werden z.B. bei Schaltplänen einer Platine oder dem Verlegen von Gas-, Wasser- und Stromanschlüssen verwendet. Das Finden eines größten planaren Subgraphen ist NP-schwer, deshalb werden Approximationsalgorithmen untersucht. Um zu bewerten, wie gut ein Approximationsalgorithmus ist, wird die Approximationsgüte verwendet, die das schlechteste Verhältnis einer vom Algorithmus gefundenen Lösung zur optimalen Lösung angibt. Ein trivialer Ansatz besteht darin, einen Spannbaum des eingegebenen Graphen zu konstruieren. Dieses Verfahren hat eine Approximationsgüte von 1/3, d.h. ein größter planarer Subgraph kann maximal dreimal so viele Kanten wie ein Spannbaum haben. Auch kompliziertere Algorithmen überbieten diese Güte nur gering; um bessere Ergebnisse zu erzielen spezialisiert man sich auf Graphen mit besonderen Eigenschaften. Ich möchte mich mit planaren Subgraphen in bipartiten Graphen beschäftigen. Vorträge und FerienakademienVorträge und Ferienakademien
|
|
TopMath
