Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 21, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Alexander Engström (KTH Stockholm)
Given a graph property, and a graph G, one can decide if G has the property by asking questions, "is (x,y) an edge of G?". If an algorithm asks the questions in a clever order, it may be able to decide if G has the property without asking about all pairs of vertices.
On the other hand, for some graph properties, there is no such algorithm. Whatever algorithm one tries, there is a graph which forces the algorithm to ask about all pairs of vertices. Such properties are called evasive.
The most rewarding methods to determine which properties are evasive, are from topological combinatorics. We will survey some of these methods, and talk about current trends and results.
Automatic MiSe System Software Version 1.4803M | admin login