89 citations · 484 across the 68 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.DS2011★ 6 cited
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
Martin Grohe, Dániel Marx
We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph as a minor to graphs excluding as a topological subgraph. We prove that for…
cs.DS2011
Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
Rajesh Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx
Given a directed graph , a set of terminals and an integer , the \textsc{Directed Vertex Multiway Cut} problem asks if there is a set of at most (nonterminal) ver…
cs.AI2011★ 24 cited
The tractability of CSP classes defined by forbidden patterns
David A. Cohen, Martin C. Cooper, Páidí Creed +1
The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort…