On space efficiency of algorithms working on structural decompositions of graphs

Prelegent(ci)

Marcin Wrochna

Afiliacja

Uniwersytet Warszawski

Termin

13 stycznia 2016 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Motivated by failed attempts at making dynamic algorithms on tree-width use less space (without using more time), we look at this from a complexity-theoretic point of view. I will mention relations to Savitch's theorem and then show how the problem of solving, say, 3-Coloring on graphs of treewidth, pathwidth, tree-depth at most s(n) is complete for classes of nondet. poly-time Turing machines with different stack access to ~s(n) memory. This gives a nice hierarchy with some corollaries.

---