3 papers
cs.CC2011
Computing hypergraph width measures exactly
Lukas Moll, Siamak Tazari, Marc Thurley
Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponenti…
cs.DM2011
Directed Nowhere Dense Classes of Graphs
Stephan Kreutzer, Siamak Tazari
We introduce the concept of shallow directed minors and based on this a new classification of classes of directed graphs which is diametric to existing directed graph decomposition…
cs.DM2009
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
Stephan Kreutzer, Siamak Tazari
Brambles were introduced as the dual notion to treewidth, one of the most central concepts of the graph minor theory of Robertson and Seymour. Recently, Grohe and Marx showed that…