- Mathematical Sciences Popularization and Education
- Books and Surveys on Parameterized Complexity
- Structural Parameterized Complexity and Combinatorics
- Kernelization
- Hypergraph Algorithms and Complexity
- Approximation
- Logic Problems
- Scheduling Problems
- Bioinformatics and Stringology
- Social Choice
- Computational Geometry
- Cryptography and Coding Theory
- Automata Theory
- Graph Minors and Well-Quasi-Ordering
- Classical Complexity Theory

Publication | BibTex | Paper | Category |
---|---|---|---|

Casey, N., and Fellows, M. R. This is Mega-Mathematics! Los Alamos National Labs, 1992. Available at http://www.c3.lanl..gov/ captors/mega-math. See also www.ccs3.lanl.gov/mega-math/write.html. | bib | _ | Mathematical Sciences Popularization and Education |

Bell, T., Fellows, M. R., and Witten, I. Computer Science Unplugged ... offline activities and games for all ages: Teacher Edition. Computer Science Unplugged, 1996. There are currently two versions of the book. The "Teachers' Edition" which is aimed at people with less of a technical background. It has 12 activities, and a lot more illustrations and handouts. Both books are available in Download from http://www.lulu.com. | bib | _ | Mathematical Sciences Popularization and Education |

Fellows, M. R., Bell, T., and Witten, I. Computer Science Unplugged ... offline activities and games for all ages: Original Activities Book. Computer Science Unplugged, 1996. | bib | _ | Mathematical Sciences Popularization and Education |

Downey, R. G., and Fellows, M. R. Parameterized Complexity. Springer-Verlag, 1999. 530 pp. | bib | _ | Books and Surveys on Parameterized Complexity |

D. Hermelin, M. Fellows and F. Rosamond. Well-Quasi-Ordering Bounded Treewidth Graphs, Proceedings IWPEC 2009, Springer-Verlag, Lecture Notes in Computer Science 5917 (2009), 149-160 | bib | paper | Graph Minors and Well-Quasi-Ordering |

Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Discrete Mathematics 230, 1-3 (2001), 215-252. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Cattell, K., Dinneen, M. J., Downey, R. G., and Fellows, M. R. On computing graph minor obstruction sets. Theoretical Computer Science 233, 1 (2000), 107-127. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Courcelle, B., Downey, R. G., and Fellows, M. R. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science 3, 11 (1997), 1194-1198. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Cattell, K., Dinneen, M. J., and Fellows, M. R. A simple linear-time algorithm for finding path-decompositions of small width. Information Processing Letters 57, 4 (1996), 197-203. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Tech. rep., 1996. Preprint. Journal publication is Discrete Mathematics (2000). | bib | paper | Graph Minors and Well-Quasi-Ordering |

Fellows, M., Kratochvil, J., Middendorf, M., and Pfeiffer, F. The complexity of induced minors and related problems. Algorithmica 13, 3 (1995), 266-282. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Cattell, K., Dinneen, M. J., and Fellows, M. R. Obstructions to within a few vertices or edges of acyclic. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS'95 (1995), S. G. Akl, F. Dehne, J.-R. Sack, and N. Santoro, Eds., vol. 955 of Lecture Notes in Computer Science, Springer-Verlag, pp. 415-427. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomial-time algorithms. Journal of Computer and System Sciences (1994), 769-779. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and well-quasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539-564. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Langston, M. A. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117-126. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R. The Robertson-Seymour theorems: A survey of applications. In CMGA: Graphs and Algorithms: Contemporary Mathematics (1989), vol. 89, AMS, pp. 1-18. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31 (1989), 1-9. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89 (1989), IEEE Computer Society Press, pp. 520-525. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M., Kinnersley, N., and Langston, M. Finite-basis theorems and a computation-integrated approach to obstruction set isolation. In Proceedings of the Third Conference on Computers and Mathematics (1989), E. Kaltofen and S. M. Watt, Eds., Springer-Verlag, pp. 37-45. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Langston, M. A. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM 35, 3 (1988), 727-739. | bib | paper | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Langston, M. A. Layout permutation problems and well-partially-ordered sets. In Proceedings of the fifth MIT conference on Advanced research in VLSI (Cambridge, MA, USA, 1988), MIT Press, pp. 315-327. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Langston, M. A. Fast self-reduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of Lecture Notes in Computer Science, Springer-Verlag, pp. 278-287. | bib | _ | Graph Minors and Well-Quasi-Ordering |

Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162. | bib | _ | Graph Minors and Well-Quasi-Ordering |

R. L. Bryant, N. G. Kinnersley, M. R. F., and Langston, M. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397-398. | bib | _ | Graph Minors and Well-Quasi-Ordering |

M. Fellows, F. Fomin and G. Gutin. Preface: Special Issue on Parameterized Complexity of Discrete Optimization, Discrete Optimization 8 (2011), 1. | bib | _ | Books and Surveys on Parameterized Complexity |

Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. | bib | paper | Books and Surveys on Parameterized Complexity |

Downey, R., Fellows, M., and Langston, M. The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors. The Computer Journal 51, 1 (2008), 1-6. The Computer Journal published a two-issue special on Parameterized Complexity that includes 15 survey articles, as well as an Introduction and Overview. The issues are Volume 51, 2008, Issue 1 and Issue 3. | bib | paper | Books and Surveys on Parameterized Complexity |

Bodlaender, H. L., Demaine, E. D., Fellows, M. R., Guo, J., Hermelin, D., Lokshtanov, D., Mller, M., Venkatesh Raman, J. v. R., and Rosamond, F. A. Open problems in parameterized and exact computation from iwpec 2008. Tech. Rep. UU-CS-2008-017, Department of Information and Computing Sciences, Utrecht University, 2008. | bib | paper | Books and Surveys on Parameterized Complexity |

ellows, M. R., and Rosamond, F. A. The complexity ecology of parameters: An illustration using bounded max leaf number. In Proceedings of Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE, Siena, Italy (2007), S. B. Cooper, B. Lwe, and A. Sorbi, Eds., vol. 4497 of Lecture Notes in Computer Science, Springer, pp. 268-277. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M., and Rosamond, F. Why is P Not Equal to NP? In Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007: Local Proceedings (2007). | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. The lost continent of polynomial time. In Proceedings of IWPEC'06 (2006), vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, p. 276 - 277. | bib | paper | Books and Surveys on Parameterized Complexity |

Dehne, F. K., Fellows, M. R., Rosamond, F. A., and Shaw, P. Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In Proceedings of Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway (2004), R. G. Downey, M. R. Fellows, and F. K. Dehne, Eds., vol. 3162 of Lecture Notes in Computer Science, Springer, pp. 271-280. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. R. A survey of FPT algorithm design techniques with an emphasis on recent advances and connections to practical computing. In Proceedings of 12th Annual European Symposium ESA, Bergen, Norway (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-2. | bib | paper | Books and Surveys on Parameterized Complexity |

Chen, J., and Fellows, M. Foreword from the Guest Editors. Journal of Computer and System Sciences 67 (2003), 653-654. Special Issue on Parameterized Complexity. | bib | _ | Books and Surveys on Parameterized Complexity |

Fellows, M. R. Blow-ups, win/win's, and crown rules: Some new directions in FPT. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'2003, Elspeet, The Netherlands (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-12. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. R. New directions and new challenges in algorithm design and complexity, parameterized. In Proceedings of Algorithms and Data Structures, 8th International Workshop WADS (2003), F. K. H. A. Dehne, J.-R. Sack, and M. H. M. Smid, Eds., vol. 2748 of Lecture Notes in Computer Science, Springer-Verlag, pp. 505-520. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. R. Parameterized complexity: The main ideas and connections to practical computing. In Experimental Algorithmics (2002), R. Fleischer, B. M. E. Moret, and E. M. Schmidt, Eds., vol. 2547 of Lecture Notes in Computer Science, Springer-Verlag, pp. 51-77. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. R. Parameterized complexity: New developments and research frontiers. In Aspects of Complexity (2001), De Gruyter, pp. 51-72. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. R. Some new developments in parameterized complexity. In Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms (2001), E. T. Baskoro, Ed., pp. 43-44. | bib | paper | Books and Surveys on Parameterized Complexity |

Fellows, M. R. Parameterized complexity: Main ideas, connections to heuristics and research frontiers. In Proceedings of ISAAC (2001), vol. 2223 of Lecture Notes in Computer Science, Springer-Verlag, pp. 291-307. | bib | paper | Books and Surveys on Parameterized Complexity |

Downey, R. G., Fellows, M. R., and Stege, U. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, vol. 49 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. DIMACS, 1999, pp. 49-99. | bib | paper | Books and Surveys on Parameterized Complexity |

Downey, R. G., Fellows, M. R., and Stege, U. Computational Tractability: A View from Mars. Tech. rep., 1999. | bib | paper | Books and Surveys on Parameterized Complexity |

Downey, R. G., and Fellows, M. R. Parameterized complexity after (almost) 10 years: Review and open questions. In Proceedings of Combinatorics, Computation and Logic, DMTCS'99 and CATS'99 (Singapore, 1999), vol. 21 of Australian Computer Science Communications, Springer-Verlag, pp. 1-33. | bib | paper | Books and Surveys on Parameterized Complexity |

Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235-276. | bib | paper | Books and Surveys on Parameterized Complexity |

Cai, L., Chen, J., Downey, R., and Fellows, M. On the structure of parameterized problems in NP. Information and Computation 123, 1 (1995), 38-49. | bib | _ | Books and Surveys on Parameterized Complexity |

Downey, R. G., and Fellows, M. R. Parameterized computational feasibility. In Proceedings of the Second Cornell Workshop on Feasible Mathematics. Feasible Mathematics II (Boston, 1995), P. Clote and J. Remmel, Eds., Birkhuser, pp. 219-244. | bib | paper paper | Books and Surveys on Parameterized Complexity |

Downey, R., and Fellows, M. R. Fixed-parameter tractability and completeness II: Completeness for W[1]. Theoretical Computer Science A 141 (1995), 109-131. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. | bib | paper | Books and Surveys on Parameterized Complexity |

Downey, R., and Fellows, M. R. Fixed-parameter tractability and completeness I: Basic theory. Siam Journal of Computing 24 (1995), 873-921. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. | bib | paper | Books and Surveys on Parameterized Complexity |

Abrahamson, K., Downey, R., and Fellows, M. R. Fixed-parameter intractability II. In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Sciences, STACS'93 (1993), vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pp. 374-385. | bib | _ | Books and Surveys on Parameterized Complexity |

Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. Computer and System Sciences (2010). To Appear. | bib | _ | Bioinformatics and Stringology |

Fellows, M. R., Hermelin, D., Rosamond, F. A., and Vialette, S. On the parameterized complexity of multiple-interval graph problems. Journal of Theoretical Computer Science 410, 1 (2009), 53-61. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Guo, J., Komusiewicz, C., Niedermeier, R., and Uhlmann, J. Graph-based data clustering with overlaps. In Proceedings of COCOON (2009), vol. 5609 of Lecture Notes in Computer Science, Springer, pp. 516-526. | bib | paper | Bioinformatics and Stringology |

M. Fellows, J. Guo and I. Kanj. The Parameterized Complexity of Some Minimum Label Problems, Proceedings WG 2009, Springer-Verlag, Lecture Notes in Computer Science 5911 (2009), 88-99. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Hartman, T., Hermelin, D., Landau, G. M., Rosamond, F. A., and Rozenberg, L. Haplotype inference constrained by plausible haplotype data. In Proceedings of the of the 20th Combinatorial Pattern Matching conference, CPM (2009), pp. 339-352. | bib | paper | Bioinformatics and Stringology |

Betzler, N., Fellows, M. R., Komusiewicz, C., and Niedermeier, R. Parameterized algorithms and hardness results for some graph motif problems. In Proceedings of Combinatorial Pattern Matching, 19th Annual Symposium, CPM, (2008), P. Ferragina and G. M. Landau, Eds., vol. 5029 of Lecture Notes in Computer Science, Springer, pp. 31-43. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In Proceedings of Automata, Languages and Programming, 34th International Colloquium, ICALP (2007), L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, Eds., vol. 4596 of Lecture Notes in Computer Science, Springer, pp. 340-351. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Fundamentals of Computation Theory, 16th International Symposium, FCT, Budapest, Hungary (2007), E. Csuhaj-Varj and Z. sik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer, pp. 312-321. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Hallett, M., and Stege, U. Analogs & duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 - 216. | bib | paper | Bioinformatics and Stringology |

Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of closest substring and related problems. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS'02 (2002), H. Alt and A. Ferreira, Eds., vol. 2285 of Lecture Notes in Computer Science, Springer-Verlag, pp. 262-273. | bib | paper | Bioinformatics and Stringology |

Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and Warnow, T. J. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science A 244, 1-2 (2000), 167-188. | bib | paper | Bioinformatics and Stringology |

Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U. Analogs and duals of the MAST problem for sequences and trees. In Proceedings of the 6th Annual European Symposium on Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P. cci, Eds., no. 1461 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 103-114. | bib | paper | Bioinformatics and Stringology |

Fellows, M., Hallett, M., and Stege, U. On the multiple gene duplication problem. In Proceedings of the 9th International Symposium on Algorithms and Computation, ISAAC'98 (1998), K.-Y. Chwa and O. H. Ibarra, Eds., vol. 1533 of Lecture Notes in Computer Science, Springer-Verlag, pp. 347-356. | bib | paper | Bioinformatics and Stringology |

Bailey, I., Cattell, K., Fellows, M. R., Koop, B., Olafson, R., Olafson, R., and Upton, C. Approaches to detection of distantly related proteins by database searches. BioTechniques 21 (1996), 1118 - 1125. | bib | _ | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 49-57. | bib | paper | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 31-54. | bib | paper | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Proceedings of Combinatorial Pattern Matching, 5th Annual Symposium, CPM (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 15-30. | bib | _ | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Proceedings of the IEEE Computer Society Workshop on Shape and Pattern Recognition in Computational Biology (1994), 99-116. IBM TJ Watson Research Center Publication. | bib | _ | Bioinformatics and Stringology |

Fellows, M. R., Hallett, M. T., and Wareham, H. T. DNA physical mapping: Three ways difficult. In Proceedings of the 1st Annual European Symposium on Algorithms, ESA '93, T. Lengauer, Ed., vol. 726 of Lecture Notes in Computer Science. Springer-Verlag, 1993, pp. 157-168. | bib | _ | Bioinformatics and Stringology |

Bodlaender, H. L., Fellows, M. R., and Warnow, T. J. Two strikes against perfect phylogeny. In Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP'92 (1992), W. Kuich, Ed., vol. 623 of Lecture Notes in Computer Science, Springer-Verlag, pp. 273-283. | bib | paper | Bioinformatics and Stringology |

Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. Fixed-parameter algorithms for Kemeny Rankings. Theoretical Computer Science (2009). 410 (2009), pp. 4554-4570. | bib | paper | Social Choice |

Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. How similarity helps to efficiently compute Kemeny Rankings. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS (2009), pp. 657-664. | bib | paper | Social Choice |

Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Fixed-parameter algorithms for Kemeny scores. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, Springer-Verlag, pp. 60-71. | bib | paper | Social Choice |

Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Computing Kemeny Rankings, parameterized by the average K-T distance. In Proceedings of the 2nd International Workshop on Computational Social Choice, COMSOC (2008). | bib | paper | Social Choice |

Christian, R., Fellows, M. R., Rosamond, F., and Slinko, A. On the complexity of lobbying in multiple referenda. Review of Economic Design 11 (2007), 217-224. | bib | paper | Social Choice |

Fellows, M. R., Rosamond, F., and Slinko, A. Sensing God's Will is fixed parameter tractable. Tech. rep., University of Auckland, New Zealand, 2008. University of Auckland, NZ Mathematics Research Report, 9 pages. | bib | paper | Social Choice |

Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixed-parameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M. R., Guo, J., Moser, H., and Niedermeier, R. A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In Proceedings of MFCS'09 (2009), vol. 5734 of Lecture Notes in Computer Science, Springer-Verlag, pp. 319-330. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Enciso, R., Fellows, M. R., Guo, J., Kanj, I., Rosamond, F., and Suchy, A. What Makes Equitable Connected Partition Easy? Proceedings IWPEC 2009, Springer-Verlag, Lecture Notes in Computer Science 5917 (2009). | bib | _ | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., and Villanger, Y. Local Search: Is Brute Force Avoidable? Proceedings International Joint Conference on Artificial Intelligence, IJCAI (2009), 486-491. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP'09 (Track A) (2009), pp. 463-474. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Parameterized low-distortion embeddings - graph metrics into lines and trees. Tech. rep., 2009. Manuscript. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Fellows, M. R., Hermelin, D., Mller, M., and Rosamond, F. A. A purely democratic characterization of W[1]. In Proceedings of Parameterized and Exact Computation, Third International Workshop IWPEC'08 (2008), M. Grohe and R. Niedermeier, Eds., vol. 5018 of Lecture Notes in Computer Science, Springer-Verlag, pp. 103-114. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgrd, L. A. Goldberg, M. M. Halldrsson, A. Inglfsdttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer, pp. 563-574. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Flum, J., Hermelin, D., Muller, M., and Rosamond, F. W-hierarchies defined by symmetric gates. Theory of Computing Systems (2008). | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of AAIM'08 (2008), vol. 5034 of Lecture Notes in Computer Science, Springer, pp. 188-199. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., and Thomassen., C. On the complexity of some colorful problems parameterized by treewidth. (invited paper). In Proceedings of First International Conference on Combinatorial Optimization and Applications COCOA'07 (2007), vol. 4616 of Lecture Notes in Computer Science, Springer-Verlag, pp. 366-377. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Cai, L., Fellows, M., Juedes, D., and Rosamond, F. The complexity of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Flum, J., Hermelin, D., Mller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D. W., Kanj, I. A., and Xia, G. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201, 2 (2005), 216-231. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., Estivill-Castro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205-218. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., and Fellows, M. R. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 1-2 (1998), 123-140. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., Fellows, M. R., and Regan, K. W. Parameterized circuit complexity and the W hierarchy. Theoretical Computer Science A 191, 1-2 (1998), 97-115. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84, 1 (1997), 119-138. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. The parameterized complexity of short computation and factorization. Archive for Mathematical Logic 36 (1997), 321-338. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R., Fellows, M., and Regan, K. Descriptive complexity and the W hierarchy. In Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, Eds., AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997, pp. 119-134. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Combinatorics, Complexity, and Logic - Proceedings of DMTCS '96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., Springer-Verlag, pp. 194-213. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Cesati, M., and Fellows, M. Sparse parameterized problems. Annals of Pure and Applied Logic 82 (1996), 1-15. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235-276. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141, 1&2 (1995), 109-131. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R., and Fellows, M. Fixed-parameter tractability and completeness III: Some structural aspects of the W hierarchy. In Complexity Theory: Current Research - Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity (Cambridge, 1993), K. Ambos-Spies, S. Homer, and U. Schning, Eds., Cambridge University Press, pp. 191-225. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Cai, L., Chen, J., Downey, R., and Fellows, M. On the structure of parameterized problems in NP. Information and Computation 123, 1 (1995), 38-49. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal of Computing 24, 4 (1995), 873-921. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. On the structure of parameterized problems in NP. In Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science, STACS'94, Caen, France (1994), P. Enjalbert, E. W. Mayr, and K. W. Wagner, Eds., vol. 775 of Lecture Notes in Computer Science, Springer, pp. 509-520. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Abrahamson, K. A., Downey, R. G., and Fellows, M. R. Fixed-parameter intractability II. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93 (1993), P. Enjalbert, A. Finkel, and K. W. Wagner, Eds., vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pp. 374-385. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Downey, R., and Fellows, M. Fixed-parameter intractability. In Proceedings of the Seventh Annual IEEE Conference on Structure in Complexity Theory (1992), pp. 36-49. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Downey, R., and Fellows, M. Fixed-parameter tractability and completeness. Congressus Numerantium 87 (1992), 161-178. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Fellows, M. R., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS'89 (1989), IEEE Computer Society Press, pp. 520-525. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Abrahamson, K. R., Fellows, M. R., Ellis, J. A., and Mata, M. E. On the complexity of fixed parameter problems. In Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS'89 (1989), IEEE Computer Society Press, pp. 210-215. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Downey, R., Fellows, M., and Mccartin, C. Parameterized approximation problems. Tech. rep. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F., Whitesides, S., and Yu, N. On the parameterized complexity of the discrete milling problem with turn costs. In Proceedings of FST TCS'09 (2009), Springer-Verlag. To Appear. | bib | _ | Computational Geometry |

M. Dom, M. F., and Rosamond, F. Parameterized complexity of stabbing rectangles and squares in the plane. In Proceedings of the 3rd Workshop on Algorithms and Computation, WALCOM'09 (2009), vol. 5431 of Lecture Notes in Computer Science, Springer-Verlag, pp. 298-309. | bib | paper | Computational Geometry |

Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D., and Whitesides, S. Faster fixed parameter tractable algorithms for matching and packing problems. Algorithmica 52, 2 (2008), 167-176. | bib | paper | Computational Geometry |

Dujmovic, V., Fellows, M. R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. Algorithmica 52, 2 (2008), 267-292. | bib | paper | Computational Geometry |

Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixed-parameter approach to 2-layer planarization. Algorithmica 45, 2 (2006), 159-182. | bib | paper | Computational Geometry |

Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixed-parameter approach to two-layer planarization. In Proceedings of the 9th International Symposium on Graph Drawing GD'01 (2001), vol. 2265 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-15. | bib | paper | Computational Geometry |

Dujmovi_, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Suderman, M., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA '01 (2001), vol. 2161 of Lecture Notes in Computer Science, Springer-Verlag, pp. 488-499. | bib | _ | Computational Geometry |

Bell, T., Fellows, M., Witten, I., and Koblitz, N. Explaining cryptographic systems to the general public. Computers and Education 40 (2003), 199-215. | bib | _ | Cryptography and Coding Theory |

Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems in coding theory. SIAM Journal of Computing 29, 2 (1999), 545-570. | bib | paper | Cryptography and Coding Theory |

Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems of linear codes and integral lattices. Tech. rep., 1997. Manuscript. | bib | paper | Cryptography and Coding Theory |

Fellows, M., and Koblitz, N. Combinatorial cryptosystems galore! In Proceedings of the Second International Symposium on Finite Fields, Las Vegas, Nevada, August, 1993 (1994), vol. 168 of Contemporary Mathematics, American Mathematical Society, pp. 51-61. | bib | paper | Cryptography and Coding Theory |

Fellows, M. R., and Koblitz, N. Fixed-parameter complexity and cryptography. In Proceedings of 10th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC'93, San Juan de Puerto Rico, Puerto Rico (1993), G. D. Cohen, T. Mora, and O. Moreno, Eds., vol. 673 of Lecture Notes in Computer Science, Springer, pp. 121-131. | bib | _ | Cryptography and Coding Theory |

Downey, R. G., Evans, P. A., and Fellows, M. R. Parameterized learning complexity. In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory (1993), ACM Press, pp. 51-57. | bib | paper | Cryptography and Coding Theory |

Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and prime factorization. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (1992), IEEE Computer Society Press, pp. 107-110. | bib | paper | Cryptography and Coding Theory |

Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and prime factorization. Designs, Codes and Cryptography 2, 3 (1992), 231-235. | bib | _ | Cryptography and Coding Theory |

Dinneen, M. J., Fellows, M. R., and Faber, V. Algebraic constructions of efficient broadcast networks. In Proceedings of Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC'91 (Berlin, Germany, 1991), H. F. Mattson, T. Mora, and T. R. N. Rao, Eds., vol. 539 of LNCS, Springer-Verlag, pp. 152-158. | bib | _ | Cryptography and Coding Theory |

Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic ideas to the general public. Computers and Education 40 (2003), 199Ñ215. | bib | paper | Mathematical Sciences Popularization and Education |

Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic systems to the general public. In Proceedings of the First IFIP World Conference on Information Security Education (WISE) (1999), L. Yngstgrm and S. Fischer-Hbner, Eds., vol. 99-008, Stockholm University Report Series, p. 221Ñ233. | bib | _ | Mathematical Sciences Popularization and Education |

Casey, N., and Fellows, M. Implementing the standards: Let's focus on the first four. DIMACS Series: Discrete Mathematics in the Schools. How Can We Have an Impact? (1997). | bib | paper | Mathematical Sciences Popularization and Education |

Fellows, M. The heart of puzzling: Mathematics and computer games. In Proceedings of the 1996 Computer Games Developers Conference (1996), Miller Freeman, p. 109Ñ120. | bib | paper | Mathematical Sciences Popularization and Education |

Fellows, M., Hibner, A., and Koblitz, N. Cultural aspects of mathematics education reform. Notices of the American Mathematics Society 41 (1994), 5Ñ9. | bib | _ | Mathematical Sciences Popularization and Education |

Fellows, M., and Koblitz, N. Kid krypto. In Proceedings of Crypto 1992 (1993), vol. 740 of Lecture Notes in Computer Science, Springer-Verlag, New York, Inc., p. 371Ñ389. | bib | paper | Mathematical Sciences Popularization and Education |

Fellows, M. Computer science in the elementary schools. In Proceedings of the Mathematicians and Education Reform Workshop, Seattle, 1991 (1993), N. Fisher, H. Keynes, and P. Wagreich, Eds., vol. 3 of Issues in Mathematics Education, Conference Board of the Mathematical Sciences, p. 143 -163. | bib | paper | Mathematical Sciences Popularization and Education |

Casey, N., and Fellows, M. R. This is Mega-Mathematics! Los Alamos National Labs, 1992. Available at http://www.c3.lanl.gov/ captors/mega-math. See also www.ccs3.lanl.gov/mega-math/write.html. | bib | paper | Mathematical Sciences Popularization and Education |

Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822-848. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M., Guo, J., Moser, H., and Niedermeier, R. A generalization of Nemhauser and Trotter's local optimization algorithm. In Proceedings of STACS'09 (2009), pp. 409-420. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Meister, D., Rosamond, F. A., Sritharan, R., and Telle, J. A. Leaf powers and their properties: Using the trees. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.-H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, Springer-Verlag, pp. 402-413. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Lokshtanov, D., Misra, N., Rosamond, F. A., and Saurabh, S. Graph layout problems parameterized by vertex cover. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.-H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, Springer-Verlag, pp. 294-305. | bib | paper | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Fellows, M. R., Heggernes, P., Mancini, F., Papadopoulos, C., and Rosamond, F. A. Clustering with partial information. In Proceedings of Mathematical Foundations of Computer Science, 33rd International Symposium, MFCS 2008, Torun, Poland (2008), E. Ochmanski and J. Tyszkiewicz, Eds., vol. 5162 of Lecture Notes in Computer Science, Springer-Verlag, pp. 144-155. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM'08 (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, Springer-Verlag, pp. 188-199. | bib | paper | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 86-96. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Fomin, F. V., Lokshtanov, D., Rosamond, F. A., Saurabh, S., Szeider, S., and Thomassen, C. On the complexity of some colorful problems parameterized by treewidth. In Proceedings of Combinatorial Optimization and Applications, COCOA'07 (2007), A. W. M. Dress, Y. Xu, and B. Zhu, Eds., vol. 4616 of Lecture Notes in Computer Science, Springer-Verlag, pp. 366-377. | bib | paper | Hypergraph Algorithms and Complexity |

Chor, B., Fellows, M. R., Ragan, M. A., Razgon, I., Rosamond, F. A., and Snir, S. Connected coloring completion for general graphs: Algorithms and complexity. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 75-85. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of 16th International Symposium Fundamentals of Computation Theory FCT'07 (2007), E. Csuhaj-Varj and Z. sik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. | bib | paper | Hypergraph Algorithms and Complexity |

Cai, L., Fellows, M., Juedes, D., and Rosamond, F. The complexity of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. | bib | paper | Hypergraph Algorithms and Complexity |

Abu-Khzam, F. N., Fellows, M. R., Langston, M. A., and Suters, W. H. Crown structures for vertex cover kernelization. Theory of Computing Systems 41, 3 (2007), 411-430. | bib | paper | Hypergraph Algorithms and Complexity |

Dehne, F., Fellows, M., Langston, M., Rosamond, F., and Stevens, K. An o(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. Theory of Computing Systems 41, 3 (2007), 479-492. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167. | bib | paper | Hypergraph Algorithms and Complexity |

Dehne, F., Fellows, M. R., Fernau, H., Prieto, E., and Rosamond, F. A. NONBLOCKER: Parameterized algorithmics for minimum dominating set. In Proceedings of Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM'06 (2006), J. Wiedermann, G. Tel, J. Pokorn_, M. Bielikov, and J. Stuller, Eds., vol. 3831 of Lecture Notes in Computer Science, Springer-Verlag, pp. 237-245. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Rosamond, F. A., Rotics, U., and Szeider, S. Clique-width minimization is NP-hard. In Proceedings of the 38th Annual Symposium on Theory of Computing, ACM'06 (2006), J. M. Kleinberg, Ed., ACM, pp. 354-362. | bib | paper | Hypergraph Algorithms and Complexity |

Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, pp. 192-202. | bib | paper | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Kernelization for convex recoloring. In Proceedings of Algorithms and Complexity in Durham, ACiD'06 (2006), H. Broersma, S. S. Dantchev, M. J. 0002, and S. Szeider, Eds., vol. 7 of Texts in Algorithmics, King's College, London, pp. 23-36. Accepted to Algorithmica. | bib | paper | Hypergraph Algorithms and Complexity |

Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F., and Stege, U. A refined search tree technique for dominating set on planar graphs. Journal of Computer and System Sciences 71, 4 (2005), 385-405. | bib | paper | Hypergraph Algorithms and Complexity |

Dehne, F. K. H. A., Fellows, M. R., Langston, M. A., Rosamond, F. A., and Stevens, K. An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of Computing and Combinatorics, 11th Annual International Conference, COCOON'05 (2005), L. Wang, Ed., vol. 3595 of Lecture Notes in Computer Science, Springer-Verlag, pp. 859-869. | bib | paper | Hypergraph Algorithms and Complexity |

Estivill-Castro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixed-parameter tractability is polynomial-time extremal structure theory I: The case of max leaf. In Proceedings of Algorithms and Complexity in Durham, ACiD 2005 (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King's College, London, pp. 1-41. | bib | paper | Hypergraph Algorithms and Complexity |

Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384. | bib | paper | Hypergraph Algorithms and Complexity |

Ellis, J., Fan, H., and Fellows, M. The dominating set problem is fixed parameter tractable for graphs of bounded genus. Journal of Algorithms 52, 2 (2004), 152-168. | bib | _ | Hypergraph Algorithms and Complexity |

Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the Vertex Cover problem: Theory and experiments. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 62-69. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F. A., Stege, U., Thilikos, D. M., and Whitesides, S. Faster fixed-parameter tractable algorithms for matching and packing problems. In Proceedings of 12th Annual European Symposium on Algorithms ESA'04 (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, Springer-Verlag, pp. 311-322. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M., Heggernes, P., Rosamond, F. A., Sloper, C., and Telle, J. A. Finding k disjoint triangles in an arbitrary graph. In Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 235-244. | bib | paper | Hypergraph Algorithms and Complexity |

Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 257-269. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., Hallett, M., and Stege, U. Analogs and duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 - 216. | bib | paper | Hypergraph Algorithms and Complexity |

Downey, R. G., Estivill-Castro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205-218. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R. Blow-ups, win/win's, and crown rules: Some new directions in FPT. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'03 (2003), H. L. Bodlaender, Ed., vol. 2880 of LNCS, Springer-Verlag, pp. 1-12. | bib | paper | Hypergraph Algorithms and Complexity |

Dehne, F., Fellows, M. R., and Rosamond, F. A. An FPT algorithm for set splitting. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'03 (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science, Springer-Verlag, pp. 180-191. | bib | paper | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Fellows, M. R., and Thilikos, D. M. Starting with nondeterminism: The systematic derivation of linear-time graph layout algorithms. In Proceedings of Mathematical Foundations of Computer Science MFCS'03 (2003), B. Rovan and P. Vojts, Eds., vol. 2747 of Lecture Notes in Computer Science, Springer, pp. 239-248. | bib | paper | Hypergraph Algorithms and Complexity |

Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of 8th Scandinavian Workshop on Algorithm Theory SWAT'02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer, pp. 150-159. | bib | paper | Hypergraph Algorithms and Complexity |

Ellis, J., Fan, H., and Fellows, M. R. The dominating set problem is fixed parameter tractable for graphs of bounded genus. In Proceedings of SWAT 2002: Scandinavian Workshop on Algorithm Theory (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of LNCS, Springer, pp. 180-189. | bib | paper | Hypergraph Algorithms and Complexity |

Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F. A., and Stege, U. A refined search tree technique for DOMINATING SET on planar graphs. In Proceedings of 26th International Symposium Mathematical Foundations of Computer Science, MFCS'01 (2001), J. Sgall, A. Pultr, and P. Kolman, Eds., vol. 2136 of Lecture Notes in Computer Science, Springer-Verlag, pp. 111-122. | bib | paper | Hypergraph Algorithms and Complexity |

Downey, R. G., Fellows, M. R., and Raman, V. The complexity of irredundant sets parameterized by size. Discrete Applied Mathematics 100, 3 (2000), 155-167. | bib | paper | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and Warnow, T. J. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science A 244, 1-2 (2000), 167-188. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings of Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS '00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 of Lecture Notes in Computer Science, Springer-Verlag, pp. 240-251. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U. Analogs and duals of the MAST problem for sequences and trees. In Proceedings of the 6th Annual European Symposium on Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P. cci, Eds., no. 1461 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 103-114. | bib | paper | Hypergraph Algorithms and Complexity |

Balasubramanian, Fellows, and Raman. An improved fixed-parameter algorithm for vertex cover. IPL: Information Processing Letters 65, 3 (1998), 163-168. | bib | paper | Hypergraph Algorithms and Complexity |

Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 1-2 (1998), 123-140. | bib | paper | Hypergraph Algorithms and Complexity |

Alon, N., Fellows, M. R., and Hare, D. R. Vertex transversals that dominate. Journal of Graph Theory 21, 1 (1996), 21-32. | bib | paper | Hypergraph Algorithms and Complexity |

Cattell, K., Dinneen, M. J., and Fellows, M. R. A simple linear-time algorithm for finding path-decompositions of small width. Information Processing Letters 57, 4 (1996), 197-203. | bib | paper | Hypergraph Algorithms and Complexity |

Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Proceedings of Combinatorics, Complexity, and Logic, DMTCS'96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., Springer-Verlag, pp. 194-213. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M., Fricke, G., Hedetniemi, S., and Jacobs, D. The private neighbor cube. SIAM Journal on Discrete Mathematics 7, 1 (1994), 41-47. | bib | _ | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94 (New York, 1994), ACM Press, pp. 449-458. | bib | paper | Hypergraph Algorithms and Complexity |

Fellows, M. R., and Langston, M. A. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117-126. | bib | _ | Hypergraph Algorithms and Complexity |

Abello, Fellows, and Stillwell. On the complexity and combinatorics of covering finite complexes. AJC: Australasian Journal of Combinatorics 4 (1991), 103-112. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M. R., and Kaschube, P. A. Searching for k3,3 in linear time. Linear and Multilinear Algebra 29, 3 (1991), 279-290. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M. R., and Hoover, M. Perfect domination. AJC: Australasian Journal of Combinatorics 3 (1991), 141-150. | bib | _ | Hypergraph Algorithms and Complexity |

Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87-101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M. R., and Wojciechowski, J. M. Counting spanning trees in directed regular multigraphs. Journal of the Franklin Institute 326 (1989), 889-896. | bib | _ | Hypergraph Algorithms and Complexity |

Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31 (1989), 1-9. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M. R., Friesen, D. K., and Langston, M. A. On finding optimal and near-optimal lineal spanning trees. Algorithmica 3, 4 (1988), 549-560. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M., Hoover, M., and Harary, F. On the galactic number of a hypercube. Mathematical and Computer Modelling 11 (1988), 212 - 215. | bib | _ | Hypergraph Algorithms and Complexity |

Bryant, R. L., Fellows, M. R., Kinnersley, N. G., and Langston, M. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397-398. | bib | _ | Hypergraph Algorithms and Complexity |

Fellows, M., Hickling, F., and Syslo, M. A topological parameterization and hard graph problems. Congressus Numerantium 59 (1987), 69-78. | bib | paper | Hypergraph Algorithms and Complexity |

Clark, L. H., Entringer, R. C., and Fellows, M. Computational complexity of integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 2 (1987), 179-191. | bib | _ | Hypergraph Algorithms and Complexity |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On Problems Without Polynomial Kernels, Journal of Computer and System Sciences 75 (2009), 423-43. | bib | _ | Kernelization |

Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixed-parameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. | bib | paper | Kernelization |

Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. | bib | paper | Kernelization |

Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822-848. | bib | paper | Kernelization |

Bodlaender, H., Fellows, M., Langston, M., Ragan, M., Rosamond, F., and Weyer, M. Quadratic Kernelization for Convex Recoloring of Trees, Algorithmica 61 (2011), 362-378. | bib | paper | Kernelization |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgrd, L. A. Goldberg, M. M. Halldrsson, A. Inglfsdttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer-Verlag, pp. 563-574. | bib | paper | Kernelization |

Abu-Khzam, F. N., Fellows, M. R., Langston, M. A., and Suters, W. H. Crown structures for vertex cover kernelization. Theory of Computing Systems 41, 3 (2007), 411-431. | bib | paper | Kernelization |

Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of Fundamentals of Computation Theory, 16th International Symposium, FCT'07 (2007), E. Csuhaj-Varj and Z. sik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. | bib | paper | Kernelization |

Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 86-96. | bib | paper | Kernelization |

Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, pp. 192-202. | bib | paper | Kernelization |

Fellows, M. The lost continent of polynomial time. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, p. 276 - 277. | bib | paper | Kernelization |

Estivill-Castro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixed-parameter tractability is polynomial-time extremal structure theory I: The case of max leaf. In Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King's College, London, pp. 1-41. | bib | paper | Kernelization |

Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384. | bib | paper | Kernelization |

Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the vertex cover problem: Theory and experiments. In Proceedings of the sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 62-69. | bib | _ | Kernelization |

Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n^{2}) steps. In Graph-Theoretic Concepts in Computer Science, 30th International Workshop WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 257-269. | bib | paper | Kernelization |

Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory SWAT'02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer-Verlag, pp. 150-159. | bib | paper | Kernelization |

Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS'00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 of Lecture Notes in Computer Science, Springer-Verlag, pp. 240-251. | bib | paper | Kernelization |

Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94 (1994), ACM Press, pp. 449-458. | bib | paper | Kernelization |

Cai, L., Fellows, M., Juedes, D., and Rosamond, F. On the efficiency of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. | bib | paper | Approximation |

Downey, R. G., Fellows, M. R., and McCartin, C. Parameterized approximation problems. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer, pp. 121-129. | bib | _ | Approximation |

Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. Theoretical Computer Science 351 (2006), 351-359. | bib | paper | Logic Problems |

Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. In Proceedings of the First International Workshop on Parameterized and Exact Computation IWPEC'04 (2004), vol. 3162 of Lecture Notes in Computer Science, Springer-Verlag, pp. 223-234. | bib | paper | Logic Problems |

Downey, R., and Fellows, M. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348. | bib | paper | Logic Problems |

Fellows, M., Downey, R., Kapron, B., Hallett, M., and Wareham, H. T. The parameterized complexity of some problems in logic and linguistics. In Proceedings of Symposium on Logical Foundations of Computer Science (LFCS) (1994), vol. 813 of Lecture Notes in Computer Science, Springer-Verlag, pp. 89 - 100. | bib | _ | Logic Problems |

Fellows, M., and McCartin, C. On the parameterized complexity of minimizing tardy tasks. Theoretical Computer Science A 298 (2003), 317-324. | bib | _ | Scheduling Problems |

Bodlaender, H., and Fellows, M. On the complexity of k-processor scheduling. Operations Research Letters 18 (1995), 93 - 98. | bib | paper | Scheduling Problems |

Fellows, M., and Langston, M. A. Processor utilization in a linearly connected parallel processing system. IEEE Transactions on Computers 37 (1988), 594 - 603. | bib | _ | Scheduling Problems |

Fellows, M., Flum, J., Hermelin, D., Mller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Hell, P., and Seyffarth, K. Constructions of dense planar networks. Networks 32 (1998), 275-281. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Alon, N., Fellows, M., and Hare, D. O. Vertex transversals that dominate. Journal of Graph Theory 21 (1996), 21-32. | bib | paper | Structural Parameterized Complexity and Combinatorics |

Fellows, M., Hell, P., and Seyffarth, K. Large planar graphs with given diameter and maximum degree. Discrete Applied Math 61 (1995), 133-153. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Campbell, L., Carlsson, G. E., Dinneen, M. J., Faber, V., Fellows, M., Langston, M. A., Moore, J. W., Mullhaupt, A. P., and Sexton, H. B. Small diameter symmetric networks from linear groups. IEEE Transactions on Computers 40 (1992), 218-220. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87-101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Dinneen, M., Faber, V., and Fellows, M. Algebraic constructions of efficient broadcast networks. In Proceedings of the Ninth International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC'91) (1991), H. F. Mattson, T. Mora, and T. Rao, Eds., vol. 539 of Lecture Notes in Computer Science, Springer-Verlag, pp. 152-158. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Fellows, M., and Kleitman, D. J. Transversals of vertex partitions in graphs. SIAM Journal of Discrete Mathematics 3 (1990), 206-215. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Fellows, M., and Kleitman, D. J. Radius and diameter in manhattan lattices. Discrete Mathematics 73 (1989), 119-125. | bib | _ | Structural Parameterized Complexity and Combinatorics |

Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finite-state computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM 2006 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384-391. | bib | _ | Automata Theory |

Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and well-quasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539-564. | bib | _ | Automata Theory |

Fellows, M., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89 (Research Triangle Park, NC) (1989), IEEE Computer Society Press, pp. 520-525. | bib | _ | Automata Theory |

Bodlaender, H., Fellows, M., and Thilikos, D. Derivation of algorithms for cutwidth and related graph layout parameters. Journal of Computer and System Sciences 75 (2009). | bib | _ | Classical Complexity Theory |

Fellows, M., Rosamond, F., Rotics, U., and Szeider, S. Cliquewidth is NP-Complete. SIAM Journal on Discrete Mathematics (SIDMA) 23, 2 (2009). A preliminary and shortened version of this paper appeared in the proceedings of STOC 2006; 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA, pp. 354Ñ362, ACM Press, 2006. This paper combines the results of the technical reports: Proving NP-Hardness for Clique-Width I: Non-approximability of Sequential Clique-width, and, Proving NP-Hardness for Clique-Width II: Non-approximability of Clique-width; Electronic Colloquium on Computational Complexity (ECCC). | bib | paper paper | Classical Complexity Theory |

Abrahamson, K. R., Fellows, M. R., and Wilson, C. B. Parallel self-reducibility. In Proceedings of Computing and Information ICCI'92, Fourth International Conference on Computing and Information (1992), W. W. Koczkodaj, P. E. Lauer, and A. A. Toptsis, Eds., IEEE Computer Society, pp. 67-70. | bib | _ | Classical Complexity Theory |

Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and certificates for primality. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (1992), IEEE Computer Society Press, pp. 107-110. | bib | paper | Classical Complexity Theory |

Abrahamson, K., Fellows, M. R., Langston, M. A., and Moret, B. M. E. Constructive complexity. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 34 (1991), 3-16. | bib | _ | Classical Complexity Theory |

Fellows, M. R., and Langston, M. A. Fast search algorithms for layout permutation problems. Integration, the VLSI Journal 12, 3 (1991), 321 - 337. | bib | _ | Classical Complexity Theory |

Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomial-time algorithms. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC'89 (1989), ACM SIGACT, ACM Press, pp. 501-512. | bib | paper | Classical Complexity Theory |

Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162. | bib | paper | Classical Complexity Theory |

Fellows, M. R., and Langston, M. A. Fast self-reduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of LNCS, Springer-Verlag, pp. 278-287. | bib | _ | Classical Complexity Theory |

Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP 2009 (Track A) (2009), pp. 463-474. | bib | paper | Bioinformatics and Stringology |

Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Parameterized low-distortion embeddings - graph metrics into lines and trees. Tech. rep., 2009. Manuscript. | bib | _ | Bioinformatics and Stringology |

Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of closest substring and related problems. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS'02 (2002), H. Alt and A. Ferreira, Eds., vol. 2285 of LNCS, Springer-Verlag, pp. 262-273. | bib | paper | Bioinformatics and Stringology |

Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finite-state computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM'96 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384-391. | bib | _ | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 31-54. | bib | paper | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 49-57. | bib | paper | Bioinformatics and Stringology |

Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Combinatorial Pattern Matching, 5th Annual Symposium, CPM'94 (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 15-30. | bib | _ | Bioinformatics and Stringology |

G. Erdelyi and M. Fellows. Parameterized Control Complexity in Bucklin Voting and in Fallback Voting, Proceedings COMSOC 2010. | _ | paper | Structural Parameterized Complexity and Combinatorics |

M. Fellows, B. Jansen, D. Lokshtanov and S. Saurabh. Determining the Winner of a Dodgson Election is Hard, Proceedings FST-TCS 2010, Leibniz International Proceedings in Informatics (2010), 459-468. | _ | paper | Structural Parameterized Complexity and Combinatorics |

M. Fellows, S. Gaspers and F. Rosamond. Parameterizing by the Number of Numbers, Proceedings IPEC 2010, Springer-Verlag, Lecture Notes in Computer Science 6478 (2010), 123-134. | _ | paper | Structural Parameterized Complexity and Combinatorics |

M. Fellows. Recent Developments in the Theory of Pre-Processing, Proceedings FAW/AAIM 2011, Springer-Verlag, Lecture Notes in Computer Science 6681 (2011), 4-5. | _ | _ | Structural Parameterized Complexity and Combinatorics |

M. Fellows, T. Friedrich, D. Hermelin, N. Narodytska and F. Rosamond. Constraint Satisfaction Problems: Convexity Makes All Different Constraints Tractable, Proceedings IJCAI 2011: 522-527. | _ | _ | Structural Parameterized Complexity and Combinatorics |

C. Bazgan, M. Chopin and M. Fellows. Parameterized Complexity of the Firefighter Problem, Proceedings ISAAC 2011, Springer-Verlag, Lecture Notes in Computer Science 7074 (2011), 643-652. | _ | _ | Structural Parameterized Complexity and Combinatorics |

R. Crowston, M. Fellows, G. Gutin, M. Jones, F. Rosamond, S. Thomasse and A. Yeo. Simultaneously Satisfying Linear Equations Over F[2]: MaxLin2 and Max-r-Lin2 Parameterized Above Average, Proceedings FST-TCS 2011 (Schloss Dagstuhl-Liebniz Centrum fuer Informatik): 229-240. | _ | _ | Structural Parameterized Complexity and Combinatorics |

L. Brueggeman, M. Fellows, R. Fleischer, M. Lackner, C. Komusiewicz, Y. Koutis, A. Pfandler and F. Rosamond. Train Marshalling is Fixed Parameter Tractable, accepted for presentation to AAAC 2012 (with no proceedings), and in Proceedings FUN 2012, Springer, Lecture Notes in Computer Science 7288 (2012), 51-56. | _ | paper | Structural Parameterized Complexity and Combinatorics |

M. Fellows, A. Pfandler, F. Rosamond and S. Ruemmele, The Parameterized Complexity of Abduction, Proceedings AAAI 2012. | _ | paper | Structural Parameterized Complexity and Combinatorics |

T. Bell, M. Fellows, J. Bell, F. Rosamond and D. Marghitu. Unplugging Education: Removing Barriers to Engaging with New Disciplines, Proceedings SDPS 2012. | _ | _ | Mathematical Sciences Popularization and Education |

M. Fellows, A. Kulik, F. Rosamond and H. Shachnai, Parameterized Approximation via Fidelity Preserving Transformations, in Proceedings ICALP 2012, Springer, Lecture Notes in Computer Science 7391 (2012), 351-362. | _ | paper | Approximation |

J. Egan, M. Fellows, F. Rosamond and P. Shaw, A Parameterized Operator on Minor Ideals: Algorithmic Consequences and Constructivity Issues, Proceedings ICTMF 2012, IERI, Lecture Notes in Information Technology 38 (2012), 312-317. | _ | _ | Structural Parameterized Complexity and Combinatorics |

M. Fellows and B. Jansen, FPT is Characterized by Useful Obstruction Sets, Proceedings WG 2013, Springer, Lecture Notes in Computer Science 8165 (2013), 261-273. | _ | _ | Structural Parameterized Complexity and Combinatorics |

M. Fellows, D. Hermelin, F. Rosamond and H. Shachnai, Tractable Parameterizations for the Minimum Linear Arrangement Problem, Proceedings ESA 2013, Springer, Lecture Notes in Computer Science 8125 (2013), 457-468. | _ | _ | Structural Parameterized Complexity and Combinatorics |

R. van Bevern, M. Fellows, S. Gaspers, M. Parsa and F. Rosamond, Myhill-Nerode Methods for Hypergraphs, Proceedings ISAAC 2013, Springer, Lecture Notes in Computer Science 8303 (2013), 372-382. | _ | _ | Hypergraph Algorithms and Complexity |

M. Fellows, J. Guo and I. Kanj. The Parameterized Complexity of Some Minimum Label Problems, Journal of Computer and System Sciences 76 (2010), 727-740. | _ | _ | Structural Parameterized Complexity and Combinatorics |

M. Fellows, J. Guo, C. Komusiewicz, R. Niedermeier and J. Uhlmann. Graph-Based Data Clustering with Overlaps, Discrete Optimization 8 (2011), 2-17. | _ | _ | _ |

M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider and C. Thomassen. On the Complexity of Some Colorful Problems Parameterized by Treewidth, Information and Computation 209 (2011), 143-153. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows and H. Fernau. Facility Location Problems: A Parameterized View, Discrete Applied Mathematics 159 (2011), 1118-1130. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, F. Fomin and G. Gutin. Preface: Special Issue on Parameterized Complexity of Discrete Optimization, Discrete Optimization 8 (2011), 1. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, J. Guo, H. Moser and R. Niedermeier. A Generalization of Nemhauser and Trotter's Local Optimization Theorem, Journal of Computer and System Sciences 77 (2011), 1141-1158. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

N. Betzler, R. van Bevern, M. Fellows, C. Komusiewicz and R. Niedermeier. Parameterized Algorithmics for Finding Connected Motifs in Biological Networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics 8 (2011), 1296-1308. | _ | _ | Bioinformatics and Stringology |

H. Bodlaender, M. Fellows, M. Langston, M. Ragan, F. Rosamond and M. Weyer. Quadratic Kernelization for Convex Recoloring of Trees, Algorithmica 61 (2011), 362-378. | _ | _ | Kernelization |

M. Fellows, D. Hermelin, G. Landau, F. Rosamond, L. Rozenberg and L. Tzvika. Haplotype Inference Constrained by Plausible Haplotype Information, IEEE/ACM Transactions on Computational Biology and Bioinformatics 8 (2011). | _ | _ | Bioinformatics and Stringology |

M. Fellows, J. Guo, H. Moser and R. Niedermeier. A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, ACM Transactions on Computation Theory 2 (2011), 5-25. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, S. Gaspers and F. Rosamond, Parameterizing by the Number of Numbers, Theory of Computing Systems 50 (2012), 675-693. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh and Y. Villanger. Local Search: Is brute-force avoidable? Journal of Computer and System Sciences 78 (2012), 707-719. | _ | _ | Structural Parameterized Complexity and Combinatorics |

M. Dom, M. Fellows, F. Rosamond and S. Sikdar. The Parameterized Complexity of Stabbing Rectangles, Algorithmica 62 (2012), 564-594. | _ | _ | Structural Parameterized Complexity and Combinatorics |

M. Fellows, D. Hermelin and F. Rosamond. Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs and their Algorithmic Applications, Algorithmica 64 (2012), 3-18. | _ | _ | Graph Minors and Well-Quasi-Ordering |

M. R. Fellows, B. M. P. Jansen and F. A. Rosamond. Towards Fully Multivariate Algorithmics: Parameter Ecology and the Deconstruction of Computational Complexity, European J. Combinatorics 34 (2013), 541-566. | _ | _ | Computational Geometry |

M. Fellows, T. Friedrich, D. Hermelin, N. Narodytska and F. Rosamond. Convexity Makes All-Different Constraints Tractable, Theoretical Computer Science, 472 (2013), 81-89. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, P. Giannopoulos, C. Knauer, C. Paul, F. Rosamond, S. Whitesides and N. Yu. On the Parameterized Complexity of the Discrete Milling Problem with Turn Costs, Journal of Discrete Algorithms, to appear. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, F. Fomin, D. Lokshtanov, E. Losievskaja, F. Rosamond and S. Saurabh. Distortion Is Fixed-Parameter Tractable, ACM Transactions on Computation Theory 5(4): 16 (2013). | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

R. Crowston, M. Fellows, G. Gutin, M. Jones, E. J. Kim, F. Rosamond, S. Thomasse, I. Z. Ruzsa and A. Yeo. Satisfying More Than Half of a System of Linear Equations Over GF [2]: A Multivariate Approach, Journal of Computer and System Sciences 80 (2014), 687-696. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

C. Bazgan, M. Chopin, M. Cygan, M. Fellows, F. Fomin and E.J. van Leeuwen. Parameterized Complexity of Firefighting Revisited, Journal of Computer and System Sciences, to appear. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

G. Erdelyi, M. Fellows, L. Piras and J. Rothe. Control Complexity in Bucklin and Fallback Voting: Theoretical Aspects, Journal of Computer and System Sciences, to appear. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

G. Erdelyi, M. Fellows, L. Piras and J. Rothe. Control Complexity in Bucklin and Fallback Voting: Experimental Aspects, Journal of Computer and System Sciences, to appear. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M.R. Fellows and B.M.P. Jansen, FPT is Characterized by Useful Obstruction Sets, ACM Transactions on Computation Theory, to appear. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

R. van Bevern, M.R. Fellows, S. Gaspers and F. Rosamond. Myhill-Nerode Methods for Hypergraphs, Algorithmica, to appear. | _ | _ | Hypergraph Algorithms and Complexity |

M. R. Fellows. Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen, Tsinghua Science and Technology 19(4) (2014), 325-328. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

R. Downey, J. Egan, M. Fellows, F. Rosamond and P. Shaw. Dynamic Dominating Set and Turbo-Charging Greedy Heuristics, Tsinghua Science and Technology 19(4) (2014), 329-337. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

Fundamentals of Parameterized Complexity, 760 pp., Springer-Verlag, 2013, with R.G. Downey. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

H.L. Bodlaender, M. Fellows, P. Heggernes, F. Mancini, C. Papadopoulos and F. Rosamond. Clustering with Partial Information, Theoretical Computer Science 411 (2010), 1202-1211. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

W-Hierarchies Defined by Symmetric Gates,Theory of Computing Systems 46 (2010), 311-339, with J. Flum, D. Hermelin, M. Mueller and F. Rosamond. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

M. Fellows, P. Giannopoulos, C. Knauer, C. Paul, F. Rosamond, S. Whitesides and N. Yu. Milling a Graph with Turn Costs: A Parameterized Complexity Perspective, Proceedings WG 2010, Springer-Verlag, Lecture Notes in Computer Science 6410 (2010), 123-134. | _ | _ | Structural Parameterized Complexity and CombinatoricsÊ |

Z-Z. Chen, M. Fellows, B. Fu, H. Jiang, Y. Liu, L. Wang and B. Zhu. A Linear Kernel for Co-Path/Cycle Packing, Proceedings of AAIM 2010, Springer-Verlag, Lecture Notes in Computer Science 6124 (2010), 90-102. | _ | _ | Kernelization |