Complexity of Tessel

One of my hobbies (I developed during my PhD) is designing boardgames. I designed three boardgames so far, one of which is Tessel, a word-building game based on graph theory. I am glad that Tessel is getting good feedback especially from schools and families. One of the most time-consuming part of Tessel’s design is deciding [...]

Read Full Post »

Graph Isomorphism, Tree Width, Path Width and LogSpace

Every once in a while, I can’t help thinking about “the complexity of graph isomorphism for bounded treewidth graphs“. Today has been one of those days again. See my earlier post to get the context. Theorem ([Das, Toran and Wagner'10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL. The proof of the above [...]

Read Full Post »