You are not logged in |
On some searching problems and related graph parameters
- Speaker(s)
- Dariusz Dereniowski
- Affiliation
- Uniwersytet Warszawski
- Date
- June 17, 2009, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
During this talk we focus on some graph searching problems. There exist several interesting connections between graph searching and graph parameters. As an example one can mention the correspondence between the minimum number of searchers required to clear a graph and pathwidth or treewidth. We are interested in some new and less examined properties. In particular, we consider, for a search strategy, the maximum vertex occupation time, i.e. the maximum number of steps a vertex is occupied (guarded) by a searcher. The corresponding graph parameter is called treespan and is closely related to the concept of elimination trees. As a second problem example we investigate a connection between the graph ranking problem (a model of graph coloring) and the maximum number of queries necessary to find an element in tree-like partial orders and partial orders with maximum element.
