On some searching problems and related graph parameters

Prelegent(ci)

Dariusz Dereniowski

Afiliacja

Uniwersytet Warszawski

Termin

17 czerwca 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---