activity
20092011
most citedFaster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs

10 citations · 12 across the 6 of their papers we have counts for

collaborators
Showing 2010Show all

2 papers · 1 filter

cs.DS2010★ 10 cited

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…

cs.LO2010★ 1 cited

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…