| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4654886 | European Journal of Combinatorics | 2007 | 4 Pages |
Abstract
We construct algorithms for deciding essentially any minor-closed parameter, with explicit time bounds. This result strengthens previous results by N. Robertson, P.D. Seymour [Graph minors. XII. Distance on a surface, Journal of Combinatorial Theory, Series B 64 (2) (1995) 240–272; Graph minors. XX. Wagner’s conjecture, Journal of Combinatorial Theory, Series B 92 (2) (2004) 325–357], M. Frick, M. Grohe [Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM 48 (6) (2001) 1184–1206], and M.R. Fellows, M.A. Langston [Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM 35 (3) (1988) 727–739] toward obtaining fixed-parameter algorithms for a general class of parameters.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Erik D. Demaine, MohammadTaghi Hajiaghayi,