Property Testing von Grapheigenschaften
| Talking persons: |
| Tobias Brunsch |
| Abstract: |
| Einige als NP-vollständig bekannte Graphprobleme lassen sich in konstanter Zeit "lösen", wenn man sie etwas abschwächt. Eine mögliche Abschwächung sieht das Konzept des Property Testings vor: Ein Property Testing Algorithmus für eine gegebene Eigenschaft muss Graphen, die die Eigenschaft besitzen, und Graphen, die hinreichend weit davon entfernt sind, die Eigenschaft zu besitzen, mit hoher Wahrscheinlichkeit korrekt klassifizieren. Der erste Teil des Konzeptvortrags der Diplomarbeit von Tobias Brunsch beschäftigt sich mit den grundlegenden Ideen, wie k-Färbbarkeit im Sinne des Property Testings getestet werden kann. Im zweiten Teil wird in Ausschnitten ein alternativer Beweis zur Existenz eines Property Testing Algorithmus für k-Färbbarkeit mit Hilfe eines Theorems vorgestellt, das eine Aussage über die Testbarkeit einer ganzen Klasse von Grapheigenschaften trifft. |
| Times: |
| Monday 6th July 2009, 6.30 pm - 8.00 pm, room 1/208 |
