Jump to main content
Chair of Theoretical Computer Science and Information Security
Chair of Theoretical Computer Science and Information Security

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