Publications

All Publications
PublicationBibTexPaperCategory
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-160bibpaperGraph 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.bibpaperGraph 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.bibpaperGraph 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.bibpaperGraph 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.bibpaperGraph 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).bibpaperGraph 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.bibpaperGraph 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.bibpaperGraph 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.bibpaperGraph 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.bibpaperGraph 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. bibpaperBooks 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.bibpaperBooks and Surveys on Parameterized Complexity
Bodlaender, H. L., Demaine, E. D., Fellows, M. R., Guo, J., Hermelin, D., Lokshtanov, D., MŸller, 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.bibpaperBooks 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. Lšwe, and A. Sorbi, Eds., vol. 4497 of Lecture Notes in Computer Science, Springer, pp. 268-277.bibpaperBooks 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).bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks and Surveys on Parameterized Complexity
Downey, R. G., Fellows, M. R., and Stege, U. Computational Tractability: A View from Mars. Tech. rep., 1999.bibpaperBooks 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.bibpaperBooks 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.bibpaperBooks 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., BirkhŠuser, pp. 219-244.bibpaper
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.bibpaperBooks 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.bibpaperBooks 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics and Stringology
Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperSocial 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.bibpaperSocial 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.bibpaperSocial 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).bibpaperSocial 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.bibpaperSocial 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.bibpaperSocial 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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., MŸller, 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.bibpaperStructural 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. DamgŒrd, L. A. Goldberg, M. M. Halld—rsson, A. Ing—lfsd—ttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer, pp. 563-574.bibpaperStructural 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).bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural Parameterized Complexity and Combinatorics
Fellows, M., Flum, J., Hermelin, D., MŸller, 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural Parameterized Complexity and Combinatorics
Cesati, M., and Fellows, M. Sparse parameterized problems. Annals of Pure and Applied Logic 82 (1996), 1-15.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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. Schšning, 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperStructural 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.bibpaperComputational 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.bibpaperComputational 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.bibpaperComputational 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.bibpaperComputational 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.bibpaperComputational 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.bibpaperCryptography 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.bibpaperCryptography 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.bibpaperCryptography 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.bibpaperCryptography 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.bibpaperCryptography 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.bibpaperMathematical 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. Yngstgršm and S. Fischer-HŸbner, 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).bibpaperMathematical 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.bibpaperMathematical 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.bibpaperMathematical 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.bibpaperMathematical 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.bibpaperMathematical 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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. bibpaperHypergraph 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. bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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. Vojt‡s, Eds., vol. 2747 of Lecture Notes in Computer Science, Springer, pp. 239-248.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph Algorithms and Complexity
Balasubramanian, Fellows, and Raman. An improved fixed-parameter algorithm for vertex cover. IPL: Information Processing Letters 65, 3 (1998), 163-168.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperHypergraph 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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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. DamgŒrd, L. A. Goldberg, M. M. Halld—rsson, A. Ing—lfsd—ttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer-Verlag, pp. 563-574.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384.bibpaperKernelization
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(n2) 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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperKernelization
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.bibpaperApproximation
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.bibpaperLogic 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.bibpaperLogic Problems
Downey, R., and Fellows, M. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348.bibpaperLogic 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.bibpaperScheduling 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., MŸller, 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.bibpaperStructural 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.bibpaperStructural 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).bibpaper
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.bibpaperClassical 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.bibpaperClassical Complexity Theory
Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162.bibpaperClassical 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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.bibpaperBioinformatics 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._paperStructural 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._paperStructural 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._paperStructural 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._paperStructural Parameterized Complexity and Combinatorics
M. Fellows, A. Pfandler, F. Rosamond and S. Ruemmele, The Parameterized Complexity of Abduction, Proceedings AAAI 2012._paperStructural 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._paperApproximation
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