10 citations · 12 across the 6 of their papers we have counts for
6 papers
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…
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…
Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
Siamak Tazari
We improve the running time of the general algorithmic technique known as Baker's approach (1994) on H-minor-free graphs from O(n^{f(|H|)}) to O(f(|H|) n^{O(1)}). The numerous appl…
Lower Bounds for the Complexity of Monadic Second-Order Logic
Stephan Kreutzer, Siamak Tazari
Courcelle's famous theorem from 1990 states that any property of graphs definable in monadic second-order logic (MSO) can be decided in linear time on any class of graphs of bounde…
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…
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
Glencora Borradaile, Erik D. Demaine, Siamak Tazari
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-conne…