Speaker |
Roman Rabinovich, I7 |
Title | Complexity Measures for Directed Graphs as Graph Searching Games |
When | 22.04.2010 |
Where | Lecture Room Informatik 11 |
Abstract | Many difficult problems, e.g., NP-complete, need to be solved in applications. Often , they are even solved “efficiently”: the running time of algorithms is not too bad. The reason for that is that most often only easy-to-handles simple instances are given as input. To distinguish between simple and complex input structures complexity measures on them are defined. For undirected graphs, the standard measure is tree-width, that has a well-studied theory and is used to construct efficient algorithms for difficult problems on simple graphs.
Complexity measures for directed graphs is currently a topic of active research. One of them is entanglement, a measure that has its roots in studying the expressive power of $\mu$-calculus. We present the general idea behind complexity measures that can be defined via graph searching games – an intuitive tool for complexity analysis of graphs. Further, we present our result about entanglement, in that we give a structural characterisation of the measure on a class of graphs. |
Slides | download |
Event calendar
- Subscribe to the ics feed.
Upcoming Events
- No Events