Property Testing für Zweifärbbarkeit von Graphen in konstanter Zeit
Vortragende(r): |
Tobias Brunsch |
Inhalt: |
Zweifärbbarkeit ist ein Problem der Graphentheorie, für das Linearzeitalgorithmen bekannt sind. Erstaunlicherweise lässt sich sogar ein O(1)-Algorithmus angeben, wenn man das Problem etwas abschwächt. Wir werden einen solchen Algorithmus anschauen und analysieren. |
Zeiten: |
Montag, der 17.11.2008, 17:15 - 18:45 Uhr, Raum 1/B006 |