Property Testing für Zweifärbbarkeit von Graphen in konstanter Zeit
Talking persons: |
Tobias Brunsch |
Abstract: |
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. |
Times: |
Monday 17th November 2008, 5.15 pm - 6.45 pm, room 1/B006 |