Navigation:
Home |
Publications |
Professional Contributions |
Outdoor Activities |
Advice for Students

@book{MegaMath_a, author = {Nancy Casey and Michael R. Fellows}, title = {This is Mega-Mathematics!}, publisher = {Los Alamos National Labs}, year = {1992}, note = {Available at http://www.c3.lanl..gov/~captors/mega-math. See also www.ccs3.lanl.gov/mega-math/write.html}, abstract = {A collection of classroom lessons in mathematics and computer science. Each lesson contains extensive background material that assumes that the topic of the lesson is new to the teacher. Topics include map coloring, graph theory, knot theory, finite state machines, algorithms, logic and infinity.} }

@book{Unplugged1, author = {Tim Bell and Michael R. Fellows and Ian Witten}, title = {Computer Science Unplugged ... offline activities and games for all ages: Teacher Edition}, publisher = {Computer Science Unplugged}, year = {1996}, abstract = {Many important topics in computer science can be taught without using computers at all. This series of activities unplugs computer science by providing off-line activities, games and puzzles that are suitable for people of all ages and backgrounds, but especially for elementary school children. The activities cover a wide range of topics, from algorithms to artificial intelligence, from binary numbers to boolean circuits, compression to cryptography.}, note = {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.} }

@book{Unplugged2, author = {Michael R. Fellows and Tim Bell and Ian Witten}, title = {Computer Science Unplugged ... offline activities and games for all ages: Original Activities Book}, publisher = {Computer Science Unplugged}, year = {1996}, abstract = {There are currently two versions of the book. This original edition is aimed for people with some technical interest. This 232-page book includes photocopy masters and detailed explanations and 20 activities. Both books have been translated into about a dozen languages. Both books are available in Download from http://www.lulu.com.} }

@book{ParameterizedComplexity, author = {Rodney G. Downey and Michael R. Fellows}, title = {Parameterized Complexity}, publisher = {Springer-Verlag}, year = {1999}, note = {530 pp.} }

@inproceedings{HermelinFellowsRosamond2009, author = {Michael R. Fellows and Danny Hermelin and Frances A. Rosamond}, title = {Well-Quasi-Ordering Bounded Treewidth Graphs}, booktitle = {Proceedings of International Workshop on Parameterized and Exact Computation, IWPEC'09}, year = {2009}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, note = {To Appear}, url = {papers/C98-wqo-iwpec.pdf} }

@article{CattellDinneenFellows2001, title = {Forbidden minors to graphs with small feedback sets}, author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows}, journal = {Discrete Mathematics}, year = {2001}, number = {1-3}, volume = {230}, pages = {215--252}, url = {papers/CDF01_MinorsSmallFVS.pdf} }

@article{CattellDinneenDowneyFellowsLangston2000, title = {On Computing Graph Minor Obstruction Sets}, author = {Kevin Cattell and Michael J. Dinneen and Rodney G. Downey and Michael R. Fellows}, journal = {Theoretical Computer Science}, year = {2000}, number = {1}, volume = {233}, pages = {107--127}, url = {papers/J48-TCS-2000.pdf} }

@article{CourcelleDowneyFellows1997, author = {B. Courcelle and R. G. Downey and M. R. Fellows}, title = {A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals}, abstract = {The major results of Robertson and Seymour on graph well-quasi-ordering establish nonconstructively that many natural graph properties that constitute ideals in the minor or immersion orders are characterized by a finite set of forbidden substructures termed the obstructions for the property. This raises the question of what general kinds of information about an ideal are sufficient, or insufficient, to allow the obstruction set for the ideal to be effectively computed. It has been previously shown that it is not possible to compute the obstruction set for an ideal from a description of a Turing machine that recognizes the ideal. This result is significantly strengthened in the case of the minor ordering. It is shown that the obstruction set for an ideal in the minor order cannot be computed from a description of the ideal in monadic second-order logic.}, journal = {Journal of Universal Computer Science}, volume = {3}, number = {11}, pages = {1194--1198}, year = {1997}, url = {papers/J42-noteGMOS.pdf} }

@article{CattellDinneenFellows1996a, author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows}, title = {A simple linear-time algorithm for finding path-decompositions of small width}, journal = {Information Processing Letters}, pages = {197--203}, year = {1996}, number = {4}, volume = {57}, publisher = {North-Holland Publishing Company}, abstract = {We describe a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^{k})$. This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.}, url = {papers/CDF96_PathDecompOfSmallWidth.pdf} }

@techreport{CattellDinneenFellows1996b, title = {Forbidden minors to graphs with small feedback sets}, author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows}, note = {Preprint. Journal publication is ``Discrete Mathematics'' (2000),}, year = {1996}, url = {papers/J52-preprint96} }

@article{FellowsKratochvilMiddendorfPfeiffer1995, author = {M. Fellows and J. Kratochvil and M. Middendorf and F. Pfeiffer}, title = {The Complexity of Induced Minors and Related Problems}, journal = {Algorithmica}, volume = {13}, number = {3}, pages = {266--282}, publisher = {Springer-Verlag, New York, Inc.}, year = {1995}, abstract = {The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning non-induced structures. The effect on these problems of restricting the input to planar graphs is also considered. The principal results include: (1) Induced maximum matching and induced directed path are NP-complete for planar graphs, (2) for every fixed graph H, induced H-minor testing can be accomplished for planar graphs $O(n)$, and (3) there are graphs H for which induced H-minor testing is NP-complete for unrestricted input. Some useful structural theorems concerning induced minors are presented, including a bound on the treewidth of planar graphs that exclude a planar induced minor.}, url = {papers/J27-inducedminors-95.ps} }

@inproceedings{CattellDinneenFellows1995, author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows}, title = {Obstructions to Within a Few Vertices or Edges of Acyclic}, abstract = {Finite obstruction sets for lower ideals in the minor order are guaranteed to exist by the Graph Minor Theorem. It has been known for several years that, in principle, obstruction sets can be mechanically computed for most natural lower ideals. In this paper, we describe a generalpurpose method for finding obstructions by using a bounded treewidth (or pathwidth) search. We illustrate this approach by characterizing certain families of cycle-cover graphs based on the two well-known problems: $k$-Feedback Vertex Set and k-Feedback Edge Set. Our search is based on a number of algorithmic strategies by which large constants can be mitigated, including a randomized strategy for obtaining proofs of minimality. 1 Introduction One of the most famous results in graph theory is the characterization of planar graphs due to Kuratowski: a graph is planar if and only if it does not contain either of K 3;3 or K 5 as a minor.}, booktitle = {Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS'95}, pages = {415--427}, year = {1995}, volume = {955}, series = {Lecture Notes in Computer Science}, editor = {Selim G. Akl and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro}, publisher = {Springer-Verlag}, url = {papers/C29-Acyclic-WADS95.ps} }

@article{FellowsLangston1994, author = {Michael R. Fellows and Michael A. Langston}, title = {On search, decision and the efficiency of polynomial-time algorithms}, journal = {Journal of Computer and System Sciences}, pages = {769--779}, year = {1994}, url = {papers/FL89_Search,Decision,Efficiency.pdf} }

@inproceedings{AbrahamsonFellows1993a, title = {Finite Automata, Bounded Treewidth and Well-Quasiordering}, author = {Karl R. Abrahamson and Michael R. Fellows}, publisher = {American Mathematical Society }, editor = {N. Robertson and P. Seymour }, booktitle = {Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991}, series = {Contemporary Mathematics}, volume = {147}, year = {1993}, pages = {539--564} }

@article{FellowsLangston1992, author = {Michael R. Fellows and Michael A. Langston}, title = {On Well-Partial-Order Theory and Its Application to Combinatorial Problems of {VLSI} Design}, journal = {SIAM Journal on Discrete Mathematics}, volume = {5}, number = {1}, pages = {117--126}, year = {1992} }

@inproceedings{Fellows1989, author = {Michael R. Fellows}, title = {The {R}obertson-{S}eymour Theorems: {A} Survey of Applications}, booktitle = {CMGA: Graphs and Algorithms: Contemporary Mathematics}, volume = {89}, publisher = {AMS}, year = {1989}, pages = {1--18} }

@article{BrownFellowsLangston1989, author = {D. J. Brown and M. R. Fellows and M. A. Langston}, title = {Polynomial-Time Self-Reducibility: Theoretical Motivations and Practical Results}, journal = {International Journal of Computer Mathematics}, volume = {31}, year = {1989}, pages = {1--9} }

@article{FellowsStueckle1989, author = {M. R. Fellows and S. Stueckle}, title = {The Immersion Order, Forbidden Subgraphs and the Complexity of Network Integrity}, journal = {Journal of Combinatorial Mathematics and Combinatorial Computing}, volume = {6}, year = {1989}, pages = {23--32} }

@inproceedings{FellowsLangston1989a, author = {M. Fellows and M. Langston}, title = {An analogue of the {M}yhill-{N}erode theorem and its use in computing finite-basis characterizations}, booktitle = {Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89}, pages = {520--525}, year = {1989}, publisher = {IEEE Computer Society Press}, abstract = {A theorem is proved that is a graph-theoretic analog of the Myhill-Nerode characterization of regular languages. The theorem is used to establish that for many applications obstruction sets are computable by known algorithms. The focus is exclusively on what is computable (by a known algorithm) in principle, as opposed to what is computable in practice.} }

@inproceedings{FellowsKinnersleyLangston1989, author = {M. Fellows and N.G. Kinnersley and M.A. Langston}, title = {Finite-Basis Theorems and a Computation-Integrated Approach to Obstruction Set Isolation}, booktitle = {Proceedings of the Third Conference on Computers and Mathematics}, pages = {37--45}, year = {1989}, publisher = {Springer-Verlag}, editor = {E. Kaltofen and S. M. Watt} }

@article{FellowsLangston1988, author = {Michael R. Fellows and Michael A. Langston}, title = {Nonconstructive tools for proving polynomial-time decidability}, journal = {Journal of the ACM}, pages = {727--739}, year = {1988}, number = {3}, volume = {35}, publisher = {ACM Press}, address = {New York}, url = {papers/FL88_NonconstructiveTOOLS.pdf} }

@inproceedings{FellowsLangston1988a, author = {Michael R. Fellows and Michael A. Langston}, title = {Layout permutation problems and well-partially-ordered sets}, booktitle = {Proceedings of the fifth MIT conference on Advanced research in VLSI}, year = {1988}, pages = {315--327}, publisher = {MIT Press}, address = {Cambridge, MA, USA} }

@inproceedings{FellowsLangston1988b, author = {Michael R. Fellows and Michael A. Langston}, title = {Fast self-reduction algorithms for combinatorial problems of {VLSI} design}, booktitle = {Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece}, pages = {278--287}, year = {1988}, volume = {319}, series = {Lecture Notes in Computer Science}, editor = {J. H. Reif}, publisher = {Springer-Verlag} }

@article{FellowsLangston1987, author = {Michael R. Fellows and Michael A. Langston}, title = {Nonconstructive advances in polynomial-time complexity}, journal = {Information Processing Letters}, pages = {157--162}, year = {1987}, number = {3}, volume = {26}, publisher = {North-Holland Publishing Company} }

@inproceedings{BryantFellowsKinnersleyLangston1987, author = {R. L. Bryant, N. G. Kinnersley, M. R. Fellows and M. A. Langston}, title = {On Finding Obstruction Sets and Polynomial-Time Algorithms for Gate Matrix Layout}, booktitle = {Proceedings of the 25th Allerton Conference on Communication, Control and Computing}, pages = {397--398}, year = {1987} }

@article{FellowsFominGutin2010, title = {Special {I}ssue on {P}arameterized {C}omplexity}, author = {Michael R. Fellows and Fedor V. Fomin and Gregory Gutin}, journal = {Discrete Optimization}, year = {2010}, note = {To Appear} }

@inproceedings{Fellows2009a, title = {The Complexity Ecology of Parameters: Some New Developments and Research Directions}, author = {Michael R. Fellows}, booktitle = {Proceedings of IWOCA}, publisher = {Springer-Verlag}, year = {2009}, note = {To Appear}, series = {Lecture Notes in Computer Science}, url = {papers/C101-IWOCA-09.pdf} }

@article{DowneyFellowsLangston2008, author = {R. Downey and M. Fellows and M. Langston}, title = {The {C}omputer {J}ournal {S}pecial {I}ssue on {P}arameterized {C}omplexity: {F}oreword by the {G}uest {E}ditors}, journal = {The Computer Journal}, year = {2008}, volume = {51}, number = {1}, pages = {1--6}, note = {{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. }, url = {papers/J71-CJforward08.pdf} }

@techreport{BodlaenderDemaineFellowsGuoHermelinLokshtanovMüllerRamanvanRooijRosamond2008, author = {Hans L. Bodlaender and Erik D. Demaine and Michael R. Fellows and Jiong Guo and Danny Hermelin and Daniel Lokshtanov and Moritz Müller and Venkatesh Raman, Johan van Rooij and Frances A. Rosamond}, year = 2008, title = {Open Problems in Parameterized and Exact Computation from IWPEC 2008}, number = {UU-CS-2008-017}, institution = {Department of Information and Computing Sciences, Utrecht University}, url = {papers/OpenProbsIWPEC08.pdf} }

@inproceedings{FellowsRosamond2007b, title = {The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number}, author = {Michael R. Fellows and Frances A. Rosamond}, booktitle = {Proceedings of Computation and Logic in the Real World, Third Conference on Computability in Europe, {C}i{E}, Siena, Italy}, publisher = {Springer}, year = {2007}, volume = {4497}, editor = {S. Barry Cooper and Benedikt L{\"o}we and Andrea Sorbi}, pages = {268--277}, series = {Lecture Notes in Computer Science}, url = {papers/FR07EcologyMaxLeaf.pdf} }

@inproceedings{FellowsRosamond2007, author = {M. Fellows and F. Rosamond}, title = {Why Is {P} {N}ot {E}qual to {NP}?}, booktitle = {Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007: Local Proceedings}, year = {2007}, url = {papers/C73.pdf} }

@inproceedings{Fellows2006a, author = {M. Fellows}, title = {The Lost Continent of Polynomial Time}, booktitle = {Proceedings of IWPEC'06}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {4169}, pages = {276 – 277}, year = {2006}, url = {papers/C70-LostContinent.pdf} }

@inproceedings{DehneFellowsRosamondShaw2004, title = {Greedy Localization, Iterative Compression, Modeled Crown Reductions: New {FPT} Techniques, an Improved Algorithm for Set Splitting, and a Novel 2$k$ Kernelization for Vertex Cover}, author = {Frank K. Dehne and Michael R. Fellows and Frances A. Rosamond and Peter Shaw}, booktitle = {Proceedings of Parameterized and Exact Computation, First International Workshop, {IWPEC} 2004, Bergen, Norway}, publisher = {Springer}, year = {2004}, volume = {3162}, editor = {Rodney G. Downey and Michael R. Fellows and Frank K. Dehne}, pages = {271--280}, series = {Lecture Notes in Computer Science}, url = {papers/DFRS04_IterativeCompresCrown.pdf} }

@inproceedings{Fellows2004, title = {A Survey of {FPT} Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing}, author = {Michael R. Fellows}, booktitle = {Proceedings of 12th Annual European Symposium ESA, Bergen, Norway}, publisher = {Springer-Verlag}, year = {2004}, volume = {3221}, editor = {Susanne Albers and Tomasz Radzik}, pages = {1--2}, series = {Lecture Notes in Computer Science}, url = {papers/C59-SurveyFPTalgDesignESA04.pdf} }

@article{ChenFellows2003, author = {J. Chen and M. Fellows}, title = {Foreword from the {G}uest {E}ditors}, journal = {Journal of Computer and System Sciences}, year = {2003}, volume = {67}, pages = {653--654}, note = {Special Issue on Parameterized Complexity,} }

@inproceedings{Fellows2003, author = {Michael R. Fellows}, title = {Blow-ups, win/win's, and crown rules: Some new directions in {FPT}}, booktitle = {Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'2003, Elspeet, The Netherlands}, pages = {1--12}, year = {2003}, volume = {2880}, series = {Lecture Notes in Computer Science}, abstract = {This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.}, editor = {Hans L. Bodlaender}, publisher = {Springer-Verlag}, url = {papers/C52-WG03.pdf} }

@inproceedings{Fellows2003b, title = {New Directions and New Challenges in Algorithm Design and Complexity, Parameterized}, author = {Michael R. Fellows}, booktitle = {Proceedings of Algorithms and Data Structures, 8th International Workshop {WADS} }, publisher = {Springer-Verlag}, year = {2003}, volume = {2748}, editor = {Frank K. H. A. Dehne and J{\"o}rg-R{\"u}diger Sack and Michiel H. M. Smid}, pages = {505--520}, series = {Lecture Notes in Computer Science}, url = {papers/C54-wads03.pdf} }

@inproceedings{Fellows2002b, title = {Parameterized Complexity: The Main Ideas and Connections to Practical Computing}, author = {Michael R. Fellows}, publisher = {Springer-Verlag}, year = {2002}, volume = {2547}, booktitle = {Experimental Algorithmics}, editor = {Rudolf Fleischer and Bernard M. E. Moret and Erik Meineche Schmidt}, pages = {51--77}, series = {Lecture Notes in Computer Science}, url = {papers/F02_Practical.pdf} }

@inproceedings{Fellows2001, author = {Michael R. Fellows}, title = {Parameterized Complexity: New Developments and Research Frontiers}, booktitle = {Aspects of Complexity}, year = {2001}, publisher = {De Gruyter}, pages = {51--72}, url = {papers/C44-Kaikoura-2000.pdf} }

@inproceedings{Fellows2001a, author = {Michael R. Fellows}, title = {Some New Developments in Parameterized Complexity}, booktitle = {Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms}, year = {2001}, editor = {Edy Tri Baskoro}, pages = {43--44}, url = {papers/C45-awoca.pdf} }

@inproceedings{Fellows2001b, title = {Parameterized Complexity: Main Ideas, Connections to Heuristics and Research Frontiers}, author = {Michael R. Fellows}, booktitle = {Proceedings of ISAAC}, publisher = {Springer-Verlag}, year = {2001}, volume = {2223}, pages = {291--307}, series = {Lecture Notes in Computer Science}, url = {papers/C46.pdf} }

@incollection{DowneyFelllowsStege99a, author = {Rodney G. Downey and Michael R. Fellows and Ulrike Stege}, title = {Parameterized Complexity: {A} Framework for Systematically Confronting Computational Intractability}, booktitle = {Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future}, year = {1999}, volume = {49}, series = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science}, publisher = {DIMACS}, pages = {49--99}, abstract = {In this paper we give a programmatic overview of parameterized computational complexity in the broad context of the problem of coping with computational intractability. We give some examples of how fixed-parameter tractability techniques can deliver practical algorithms in two different ways: (1) by providing useful exact algorithms for small parameter ranges, and (2) by providing guidance in the design of heuristic algorithms. In particular, we describe an improved FPT kernelization algorithm for Vertex Cover, a practical FPT algorithm for the Maximum Agreement Subtree (MAST) problem parameterized by the number of species to be deleted, and new general heuristics for these problems based on FPT techniques. In the course of making this overview, we also investigate some structural and hardness issues. We prove that an important naturally parameterized problem in artificial intelligence, STRIPS Planning (where the parameter is the size of the plan) is complete for $W [1]$. As a corollary, this implies that $k$-Step Reachability for Petri Nets is complete for $W [1]$. We describe how the concept of treewidth can be applied to STRIPS Planning and other problems of logic to obtain FPT results. We describe a surprising structural result concerning the top end of the parameterized complexity hierarchy: the naturally parameterized Graph $k$-Coloring problem cannot be resolved with respect to XP either by showing membership in XP, or by showing hardness for XP without settling the P = NP question one way or the other.}, url = {papers/DFS99_Framework.pdf} }

@techreport{DowneyFellowsStege99b, author = {Rodney G. Downey and Michael R. Fellows and Ulrike Stege}, title = {Computational {T}ractability: {A} {V}iew From {M}ars}, url = {papers/ViewFromMars.ps}, year = {1999} }

@inproceedings{DowneyFellows1999, title = {Parameterized Complexity After (Almost) 10 Years: Review and Open Questions}, author = {Rodney G. Downey and Michael R. Fellows}, booktitle = {Proceedings of Combinatorics, Computation and Logic, DMTCS'99 and CATS'99}, publisher = {Springer-Verlag}, address = {Singapore}, year = {1999}, volume = {21}, pages = {1--33}, series = {Australian Computer Science Communications}, url = {papers/DF99_AfterTenYears.pdf} }

@article{DowneyFellows1995e, author = {K.. Abrahamson and Rodney G. Downey and Michael R. Fellows}, title = {Fixed-Parameter Tractability and Completeness {IV}: On Completeness for {W[P]} and {PSPACE} Analogs}, journal = {Annals of Pure and Applied Logic}, volume = {73}, year = {1995}, pages = {235-276}, url = {papers/J31-fpt4-95.pdf} }

@article{CaiChenDowneyFellows1995a, title = {On the Structure of Parameterized Problems in {NP}}, author = {Liming Cai and Jianer Chen and Rodney Downey and Michael Fellows}, pages = {38--49}, journal = {Information and Computation}, year = {1995}, volume = {123}, number = {1}, abstract = {Fixed-parameter intractability of optimization problems in NP is studied based on computational models with limited nondeterminism. Strong evidence is shown that many NP optimization problems are not fixed-parameter tractable and that the fixed-parameter intractability hierarchy (the $W$-hierarchy) does not collapse.} }

@inproceedings{DowneyFellows1995a, author = {R. G. Downey and M. R. Fellows}, title = {Parameterized Computational Feasibility}, abstract = {Many natural computational problems have input consisting of two or more parts. For example, the input might consist of a graph and a positive integer. For many natural problems we may view one of the inputs as a parameter and study how the complexity of the problem varies if the parameter is held fixed. For many applications of computational problems involving such a parameter, only a small range of parameter values is of practical significance, so that fixed parameter complexity is a natural concern. In studying the complexity of such problems, it is therefore important to have a framework in which we can make qualitative distinctions about the contribution of the parameter to the complexity of the problem. In this paper we survey one such framework for investigating parameterized computational complexity and present a number of new results for this theory.}, booktitle = {Proceedings of the Second Cornell Workshop on Feasible Mathematics. Feasible Mathematics II}, editor = {P. Clote and J.. Remmel}, pages = {219--244}, publisher = {Birkh{\"a}user}, address = {Boston}, year = {1995}, url = {papers/C17-feasibility95.ps} }

@article{DowneyFellows1995b, author = {Rodney Downey and Michael R. Fellows}, title = {Fixed-Parameter Tractability and Completeness {II}: Completeness for {W[1]}}, journal = {Theoretical Computer Science A}, volume = {141}, year = {1995}, pages = {109-131}, note = {Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991.}, url = {papers/J30-CompletenessII-95.ps} }

@article{DowneyFellows1995c, author = {Rodney Downey and Michael R. Fellows}, title = {Fixed-Parameter Tractability and Completeness {I}: Basic Theory}, journal = {Siam Journal of Computing}, volume = {24}, year = {1995}, pages = {873-921}, note = {Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991.}, url = {papers/J29-completeness1-95.ps} }

@inproceedings{AbrahamsonDowneyFellows1993a, author = {Karl Abrahamson and Rodney Downey and Michael R. Fellows}, title = {Fixed-Parameter Intractability {II}}, booktitle = {Proceedings of the 10th Symposium on Theoretical Aspects of Computer Sciences, STACS'93}, volume = {665}, year = {1993}, pages = {374-385}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science} }

@article{FellowsFertinHermelinVialette2010, title = {Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs}, author = {Michael R. Fellows and Guillaume Fertin and Danny Hermelin and St{\'e}phane Vialette}, journal = {Computer and System Sciences}, year = {2010}, note = {To Appear} }

@article{FellowsHermelinRosamondVialette2009, author = {Michael R. Fellows and Danny Hermelin and Frances A. Rosamond and St{\'e}phane Vialette}, title = {On the Parameterized Complexity of Multiple-Interval Graph Problems}, journal = {Journal of Theoretical Computer Science}, volume = {410}, number = {1}, year = {2009}, pages = {53-61}, url = {papers/J77-TCS-later.pdf} }

@inproceedings{FellowsGuoKomusiewiczNiedermeierUhlmann2009, author = {Michael R. Fellows and Jiong Guo and Christian Komusiewicz and Rolf Niedermeier and Johannes Uhlmann}, title = {Graph-Based Data Clustering with Overlaps}, booktitle = {Proceedings of COCOON}, year = {2009}, pages = {516-526}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {5609}, url = {papers/C95-overlap-clustering.pdf} }

@inproceedings{FellowsGuoKanj2009, author = {Michael R. Fellows and Jiong Guo and Iyad Kanj}, title = {The Parameterized Complexity of some Minimum Label Problems}, booktitle = {Proceedings of WG}, year = {2009}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, note = {To Appear}, url = {papers/C97.pdf} }

@inproceedings{FellowsHartmanHermelinLandauRosamondRozenberg2009, author = {Michael R. Fellows and Tzvika Hartman and Danny Hermelin and Gad M. Landau and Frances A. Rosamond and Liat Rozenberg}, title = {Haplotype Inference Constrained by Plausible Haplotype Data}, booktitle = {Proceedings of the of the 20th Combinatorial Pattern Matching conference, CPM}, year = {2009}, pages = {339-352}, url = {papers/C93-Haplotype-CPM09.pdf} }

@inproceedings{BetzlerFellowsKomusiewiczNiedermeier2008, title = {Parameterized Algorithms and Hardness Results for Some Graph Motif Problems}, author = {Nadja Betzler and Michael R. Fellows and Christian Komusiewicz and Rolf Niedermeier}, booktitle = {Proceedings of Combinatorial Pattern Matching, 19th Annual Symposium, CPM,}, publisher = {Springer}, year = {2008}, volume = {5029}, editor = {Paolo Ferragina and Gad M. Landau}, pages = {31--43}, series = {Lecture Notes in Computer Science}, url = {papers/C84-motifs.pdf} }

@inproceedings{FellowsFertinHermelinVialette2007, title = {Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs}, author = {Michael R. Fellows and Guillaume Fertin and Danny Hermelin and St{\'e}phane Vialette}, booktitle = {Proceedings of Automata, Languages and Programming, 34th International Colloquium, ICALP}, publisher = {Springer}, year = {2007}, volume = {4596}, editor = {Lars Arge and Christian Cachin and Tomasz Jurdzinski and Andrzej Tarlecki}, pages = {340--351}, series = {Lecture Notes in Computer Science}, url = {papers/C77-ICALP-07} }

@inproceedings{FellowsLangstonRosamondShaw2007, title = {Efficient Parameterized Preprocessing for Cluster Editing}, author = {Michael R. Fellows and Michael A. Langston and Frances A. Rosamond and Peter Shaw}, booktitle = {Fundamentals of Computation Theory, 16th International Symposium, {FCT}, Budapest, Hungary}, publisher = {Springer}, year = {2007}, volume = {4639}, editor = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Zolt{\'a}n {\'E}sik}, pages = {312--321}, series = {Lecture Notes in Computer Science}, url = {papers/C78-FCT07.pdf} }

@article{FellowsGrammNiedermeier2006, author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier}, title = {On The Parameterized Intractability Of Motif Search Problems}, journal = {Combinatorica}, volume = {26}, number = {2}, year = {2006}, pages = {141--167}, publisher = {Springer-Verlag New York, Inc.}, url = {papers/FGN06_MotifSearch.pdf} }

@article{FellowsHallettStege2003, author = {M. R. Fellows and M. Hallett and U. Stege}, title = {Analogs \& Duals of the {MAST} Problem for Sequences \& Trees}, journal = {Journal of Algorithms}, volume = {49}, year = {2003}, pages = {192 -- 216}, url = {papers/J54-MASTanalogs.pdf} }

@inproceedings{FellowsGrammNiedermeier2002, author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier}, title = {On the Parameterized Intractability of Closest Substring and Related Problems}, abstract = {We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is $W[1]$-hard with respect to the number $k$ of input strings (even over a binary alphabet). This problem is therefore unlikely to be solvable in time $O(f(k)n)$ for any function $f$ and constant $c$ independent of $k$. Effectively, the problem can be expected to be intractable, in any practical sense, for k 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NP-complete and both possess polynomial time approximation schemes. We also prove $W[1]$-hardness for other parameterizations in the case of unbounded alphabet size. Our main $W[1]$-hardness result generalizes to Consensus Patterns, a problem of similar significance in computational biology.}, booktitle = {Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS'02}, pages = {262--273}, year = {2002}, volume = {2285}, series = {Lecture Notes in Computer Science}, editor = {Helmut Alt and Afonso Ferreira}, publisher = {Springer-Verlag}, url = {papers/C48-stacs02-substrings.pdf} }

@article{BodlaenderFellowsHallettWarehamWarnow2000, author = {Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett and H. Todd Wareham and Tandy J. Warnow}, title = {The Hardness of Perfect Phylogeny, Feasible Register Assignment and other problems on Thin Colored Graphs}, journal = {Theoretical Computer Science A}, abstract = {In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has as a characteristic a uniform upper bound on the tree or path width of the graphs in {"}yes{"}-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for the complexity classes W [t] for all t 2 N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.}, volume = {244}, number = {1--2}, pages = {167--188}, year = {2000}, url = {papers/BFHWW00_PhylogenyThinColoredGraphs.pdf} }

@inproceedings{FellowsHallettKorostenskyStege1998, author = {M. Fellows and M. T. Hallett and C. Korostensky and U. Stege}, title = {Analogs and Duals of the {MAST} Problem for Sequences and Trees}, abstract = {Two natural kinds of problems about {"}structured collections of symbols{"} can be generally refered to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as leaf-labels and a subobject is defined by label-respecting hereditary topological containment, both of these problems are NP-complete, as are the analogous problems for sequences (the well-known Longest Common Subsequence and Shortest Common Supersequence problems). However, when the trees are restricted by allowing each symbol to occur as a leaf-label at most once (which we call a phylogenetic tree or p-tree), then the Largest Common Subobject problem, better known as the Maximum Agreement Subtree (MAST) problem, is solvable in polynomial time. We explore the complexity of the basic subobject and superobject problems for sequences and binary trees.}, booktitle = {Proceedings of the 6th Annual European Symposium on Algorithms}, editor = {G. Bilardi and G. F. Italiano and A. Pietracaprina and G. Pu cci}, series = {Lecture Notes in Computer Science}, number = {1461}, publisher = {Springer-Verlag, Berlin}, year = {1998}, pages = {103--114}, url = {papers/C36.pdf} }

@inproceedings{FellowsHallettStege1998, author = {Michael Fellows and Michael Hallett and Ulrike Stege}, title = {On the multiple gene duplication problem}, abstract = {A fundamental problem in computational biology is the determination of the correct species tree for a set of taxa given a set of (possibly contradictory) gene trees. In recent literature, the Duplication/ Loss model has received considerable attention. Here one measures the similarity/dissimilarity between a set of gene trees by counting the number of paralogous gene duplications and subsequent gene losses which need to be postulated in order to explain (in an evolutionarily meaningful way) how the gene trees could have arisen with respect to the species tree. Here we count the number of multiple gene duplication events (duplication events in the genome of the organism involving one or more genes) without regard to gene losses. Multiple Gene Duplication asks to find the species tree S which requires the fewest number of multiple gene duplication events to be postulated in order to explain a set of gene trees G1 ; G2 ; : : : ; Gk . We also examine related problems.}, booktitle = {Proceedings of the 9th International Symposium on Algorithms and Computation, ISAAC'98}, pages = {347--356}, year = {1998}, volume = {1533}, series = {Lecture Notes in Computer Science}, editor = {Kyung-Yong Chwa and Oscar H. Ibarra}, publisher = {Springer-Verlag}, url = {papers/C37-multiplegene-ISAAC98.pdf} }

@article{BaileyCattellFellowsKoopOlafsonOlafsonUpton1996, author = {I. Bailey and K. Cattell and M. R. Fellows and B. Koop and R. Olafson and R.W. Olafson and C. Upton}, title = {Approaches to Detection of Distantly Related Proteins by Database Searches}, journal = {BioTechniques}, volume = {21}, year = {1996}, pages = {1118 -- 1125} }

@article{BodlaenderDowneyFellowsHallettWareham1995, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.. Fellows and Michael T. Hallett and Harold T. Wareham}, title = {Parameterized Complexity Analysis in Computational Biology}, journal = {Computer Applications in the Biosciences}, volume = {11}, number = {1}, year = {1995}, pages = {49-57}, url = {papers/BDFHW95CompBio.pdf} }

@article{BodlaenderDowneyFellowsWareham1995, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Harold T. Wareham}, title = {The Parameterized Complexity of Sequence Alignment and Consensus}, journal = {Theoretical Computer Science}, volume = {147}, number = {1{\&}2}, year = {1995}, pages = {31-54}, url = {papers/C25-SeqAlign94.pdf} }

@inproceedings{BodlaenderDowneyFellowsWareham1994, title = {The Parameterized Complexity of Sequence Alignment and Consensus}, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Harold T. Wareham}, booktitle = {Proceedings of Combinatorial Pattern Matching, 5th Annual Symposium, {CPM} }, publisher = {Springer}, year = {1994}, volume = {807}, editor = {Maxime Crochemore and Dan Gusfield}, pages = {15--30}, series = {Lecture Notes in Computer Science} }

@article{BodlaenderDowneyFellowsHallettWareham1994, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.. Fellows and Michael T. Hallett and Harold T. Wareham}, title = {Parameterized Complexity Analysis in Computational Biology}, journal = {Proceedings of the IEEE Computer Society Workshop on Shape and Pattern Recognition in Computational Biology}, year = {1994}, pages = {99-116}, publisher = {Plenum Press}, note = {IBM TJ Watson Research Center Publication} }

@incollection{FellowsHallettWareham1993, author = {Michael R. Fellows and Michael T. Hallett and H. Todd Wareham}, title = {{DNA} Physical Mapping: Three Ways Difficult}, booktitle = {Proceedings of the 1st Annual European Symposium on Algorithms, ESA '93}, pages = {157--168}, year = {1993}, volume = {726}, series = {Lecture Notes in Computer Science}, editor = {Thomas Lengauer}, publisher = {Springer-Verlag} }

@inproceedings{BodlaenderFellowsWarnow1992, author = {Hans L. Bodlaender and Mike R. Fellows and Tandy J. Warnow}, title = {Two Strikes Against Perfect Phylogeny}, booktitle = {Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP'92}, pages = {273--283}, year = {1992}, volume = {623}, series = {Lecture Notes in Computer Science}, editor = {W. Kuich}, publisher = {Springer-Verlag}, url = {papers/BFW92_Phylogeny.pdf} }

@article{BetzlerFellowsGuoNiedermeierRosamond2009, author = {N. Betzler and M. R. Fellows and J. Guo and R. Niedermeier and F. Rosamond}, title = {Fixed-Parameter Algorithms for {K}emeny {R}ankings}, journal = {Theoretical Computer Science}, year = {2009}, note = {Accepted for publication, August 2009, 30 pages}, url = {papers/J81-KemenyRankings09.pdf} }

@inproceedings{BetzlerFellowsGuoNiedermeierRosamond2009b, author = {Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond}, title = {How Similarity Helps to Efficiently Compute {K}emeny {R}ankings}, booktitle = {Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS}, year = {2009}, pages = {657-664}, url = {papers/C92-Betzler-AAMAS09.pdf} }

@inproceedings{BetzlerFellowsGuoNiedermeierRosamond2008, title = {Fixed-Parameter Algorithms for {K}emeny Scores}, author = {Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond}, booktitle = {Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, {AAIM}}, publisher = {Springer-Verlag}, year = {2008}, volume = {5034}, editor = {Rudolf Fleischer and Jinhui Xu}, pages = {60--71}, series = {Lecture Notes in Computer Science}, url = {papers/C81-AAIM08.pdf} }

@inproceedings{BetzlerFellowsGuoNiedermeierRosamond2008a, title = {Computing {K}emeny {R}ankings, Parameterized by the Average {K-T} Distance}, author = {Nadja Betzler and Michael R. Fellows and Jiong Guo and Rolf Niedermeier and Frances A. Rosamond}, booktitle = {Proceedings of the 2nd International Workshop on Computational Social Choice, COMSOC}, year = {2008}, url = {papers/C87-AveKT-COMSOC08.pdf} }

@article{ChristianFellowsRosamondSlinko2007, author = {R. Christian and M. R. Fellows and F. Rosamond and A. Slinko}, title = {On the Complexity of Lobbying in Multiple Referenda}, journal = {Review of Economic Design}, year = {2007}, volume = {11}, pages = {217--224}, url = {papers/J68-CFRS-RevEcD07.pdf} }

@techreport{FellowsRosamondSlinko2008, author = {M. R. Fellows and F. Rosamond and A. Slinko}, title = {Sensing {G}od's {W}ill is Fixed Parameter Tractable}, note = {University of Auckland, NZ Mathematics Research Report, 9 pages}, institution = {University of Auckland, New Zealand}, year = {2008}, url = {papers/C103-Slinko-Sensing.pdf} }

@inproceedings{FellowsHromkovicRosamondSteinova2009a, title = {Fixed-Parameter Tractability, Relative Kernelization and the Effectivization of Structural Connections}, author = {M. Fellows and J. Hromkovic and F. Rosamond and M. Steinova}, booktitle = {Proceedings of CiE'09}, publisher = {Springer-Verlag}, year = {2009}, note = {To Appear}, series = {Lecture Notes in Computer Science}, url = {papers/C102-Cie09abstract.pdf} }

@inproceedings{FellowsGuoMoserNiedermeier2009a, author = {Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier}, title = {A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems}, booktitle = {Proceedings of MFCS'09}, year = {2009}, pages = {319-330}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {5734}, url = {papers/C99-mfcs09-dichotomy.pdf} }

@inproceedings{EncisoFellowsGuoKanjRosamondSuchy2009, author = {R. Enciso and M. R. Fellows and J. Guo and I. Kanj and F. Rosamond and A. Suchy}, title = {What Makes Equitable Connected Partition Easy?}, booktitle = {Proceedings of International Workshop of Parameterized and Exact Computation, IWPEC'09}, year = {2009}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, note = {To Appear} }

@inproceedings{FellowsFominLokshtanovRosamondSaurabhVillanger2009, author = {M. Fellows and F. V. Fomin and D. Lokshtanov and F. Rosamond and S. Saurabh and Y. Villanger}, title = {Local Search: Is Brute Force Avoidable?}, booktitle = {Proceedings International Joint Conference on Artificial Intelligence, IJCAI'09}, year = {2009}, note = {To Appear}, url = {papers/C94-local-search.pdf} }

@inproceedings{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009a, author = {Michael R. Fellows and Fedor V. Fomin and Daniel Lokshtanov and Elena Losievskaja and Frances A. Rosamond and Saket Saurabh}, title = {Distortion Is Fixed Parameter Tractable}, booktitle = {Proceedings of ICALP'09 (Track A)}, year = {2009}, pages = {463-474}, url = {papers/C96.pdf} }

@techreport{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009b, title = {Parameterized Low-distortion Embeddings - Graph Metrics into Lines and Trees}, author = {Michael Fellows and Fedor Fomin and Daniel Lokshtanov and Elena Losievskaja and Frances A. Rosamond and Saket Saurabh}, note = {Manuscript}, year = {2009}, abstract = {We describe algorithms for finding a low distortion non-contracting embedding of $M$ into line and tree metrics. We give an $O(nd^4(2d+1)^{2d})$ time algorithm that for an unweighted graph metric $M$ and integer $d$ either constructs an embedding of $M$ into the line with distortion at most $d$, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is $O(n(dW)^4(2d+1)^{2dW})$ where $W$ is the largest edge weight of the input graph. We also show that deciding whether a weighted graph metric $M(G)$ with maximum weight $W < |V(G)|$ can be embedded into the line with distortion at most $d$ is NP-Complete for every fixed rational $d \geq 2$. This rules out any possibility of an algorithm with running time $O((nW)^{h(d)})$ where $h$ is a function of $d$ alone. We generalize the result on embedding into the line by proving that for any tree $T$ with maximum degree $\Delta$, embedding of $M$ into a shortest path metric of $T$ is FPT, parameterized by $(\Delta,d)$.} }

@inproceedings{FellowsHermelinMullerRosamond2008, title = {A Purely Democratic Characterization of {W}[1]}, author = {Michael R. Fellows and Danny Hermelin and Moritz M{\"u}ller and Frances A. Rosamond}, booktitle = {Proceedings of Parameterized and Exact Computation, Third International Workshop IWPEC'08}, publisher = {Springer-Verlag}, year = {2008}, volume = {5018}, editor = {Martin Grohe and Rolf Niedermeier}, pages = {103--114}, series = {Lecture Notes in Computer Science}, url = {papers/C82-democratic.pdf} }

@inproceedings{BodlaenderDowneyFellowsHermelin2008, title = {On Problems Without Polynomial Kernels}, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Danny Hermelin}, booktitle = {Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games}, publisher = {Springer}, year = {2008}, volume = {5125}, editor = {Luca Aceto and Ivan Damg{\aa}rd and Leslie Ann Goldberg and Magn{\'u}s M. Halld{\'o}rsson and Anna Ing{\'o}lfsd{\'o}ttir and Igor Walukiewicz}, pages = {563--574}, series = {Lecture Notes in Computer Science}, url = {papers/C85-ICALP-08.pdf} }

@article{FellowsFlumHermelinMullerRosamond2008, title = {W-Hierarchies Defined by Symmetric Gates}, author = {M. Fellows and J. Flum and D. Hermelin and M. Muller and F. Rosamond}, journal = {Theory of Computing Systems}, abstract = {Originally defined via the weighted satisfiability problem for Boolean circuits, the classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. Here, besides the Boolean connectives, we consider connectives such as majority, not-all-equal, and unique. For example, a gate labelled by the majority connective outputs true if more than half of its inputs are true. For any finite set of connectives we construct the corresponding W(x)-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W(x)-hierarchy coincide levelwise. If only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.}, year = {2008}, url = {papers/J74-TOCS-comb-circs-revised.pdf} }

@inproceedings{FellowsFernau2008a, title = {Facility Location Problems: A Parameterized View}, author = {Michael Fellows and Henning Fernau}, booktitle = {Proceedings of AAIM'08}, pages = {188--199}, year = {2008}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {5034}, url = {papers/C83-Facilities-AAIM08.pdf} }

@inproceedings{FellowsFominLokshtanovRosamondSaurabhSzeiderThomassen2007a, title = {On the Complexity of Some Colorful Problems Parameterized by Treewidth. (invited paper) }, author = {M. Fellows and F. V. Fomin and D. Lokshtanov and F. Rosamond and S. Saurabh and S. Szeider and C. Thomassen. }, booktitle = {Proceedings of First International Conference on Combinatorial Optimization and Applications COCOA'07}, pages = {366--377}, year = {2007}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {4616}, abstract = {We study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph: 1) The list chromatic number $\chi_l(G)$ of a graph $G$ is defined to be the smallest positive integer $r$, such that for every assignment to the vertices $v$ of $G$, of a list $L_v$ of colors, where each list has length at least $r$, there is a choice of one color from each vertex list $L_v$ yielding a proper coloring of $G$. We show that the problem of determining whether $\chi_l(G)\leq r$, the LIST CHROMATIC NUMBER problem, is solvable in linear time for every fixed treewidth bound $t$. The method by which this is shown is new and of general applicability. 2) The LIST COLORING problem takes as input a graph $G$, together with an assignment to each vertex $v$ of a set of colors $C_v$. The problem is to determine whether it is possible to choose a color for vertex $v$ from the set of permitted colors $C_v$ , for each vertex, so that the obtained coloring of $G$ is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of $G$. The closely related PRECOLORING EXTENSION problem is also shown to be W[1]-hard, parameterized by treewidth. 3) An equitable coloring of a graph $G$ is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by $(t, r)$. We also show that a list-based variation, LIST EQUITABLE COLORING is W[1]-hard for trees, parameterized by the number of colors on the lists.}, url = {papers/ C79-coloring-cocoa07.pdf} }

@article{CaiFellowsJuedesRosamond2007, title = {The Complexity of Polynomial-Time Approximation}, author = {Liming Cai and Michael Fellows and David Juedes and Frances Rosamond}, year = {2007}, journal = {Theory of Computing Systems}, volume = {41}, number = {3}, pages = {459--477}, publisher = {Springer-Verlag, New York, Inc.}, abstract = {In 1996, Khanna and Motwani proposed three logic-based optimization problems constrained by planar structure, and offered the hypothesis that these putatively fundamental problems might provide insight intocharacterizing the class of optimization problems that admit a polynomial-time approximation scheme (PTAS). This paper explores this program from the point of view of parameterized complexity. Problems of optimization are naturally parameterized by the parameter $k = 1/{$\epsilon$}$. We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.}, url = {papers/J67-CFJR_jcss(old).pdf} }

@inproceedings{FellowsFlumHermelinMullerRosamond2007a, author = {Michael Fellows and J{\"o}rg Flum and Danny Hermelin and Moritz M{\"u}ller and Frances Rosamond}, title = {Parameterized Complexity via Combinatorial Circuits}, booktitle = {Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop}, pages = {55--67}, year = {2007}, editor = {Hajo Broersma and Stefan Dantchev and Matthew Johnson and Stefan Szeider}, volume = {9}, series = {Texts in Algorithmics}, publisher = {College Publications London}, url = {papers/C80-ACiD07-Circuits.pdf} }

@article{ChenChorFellowsHuangJuedesKanjXia2005, title = {Tight Lower Bounds for certain Parameterized {NP}-Hard Problems}, author = {Jianer Chen and Benny Chor and Mike Fellows and Xiuzhen Huang and David W. Juedes and Iyad A. Kanj and Ge Xia}, journal = {Information and Computation}, year = {2005}, number = {2}, volume = {201}, pages = {216--231}, url = {papers/CCFHJKX05_TightLowerBounds.pdf} }

@article{DowneyEstivill-CastroFellowsPrietoRosamond2003, title = {Cutting Up is Hard to Do: the Parameterized Complexity of {k}-Cut and Related Problems}, author = {Rodney G. Downey and Vladimir Estivill-Castro and Michael R. Fellows and Elena Prieto and Frances A. Rosamond}, journal = {Electronic Notes in Theoretical Computer Science}, year = {2003}, volume = {78}, pages = {205--218}, url = {papers/DEPR03_kcut.pdf} }

@article{DowneyFellows2001a, title = {Index Sets and Parametric Reductions}, author = {Rodney G. Downey and Michael R. Fellows}, journal = {Archive for Mathematical Logic}, year = {2001}, number = {5}, volume = {40}, pages = {329--348}, url = {papers/J51-IndexSets01.pdf} }

@article{DowneyFellows1998, author = {Rodney G. Downey and Michael R. Fellows}, title = {Threshold Dominating Sets and an Improved Characterization of {W}[2]}, journal = {Theoretical Computer Science}, pages = {123--140}, year = {1998}, number = {1-2}, volume = {209}, publisher = {Elsevier Science Publishers}, url = {papers/J46-wstar2.pdf} }

@article{DowneyFellowsRegan1998, author = {Rodney G. Downey and Michael R. Fellows and Kenneth W. Regan}, title = {Parameterized Circuit Complexity and the {W} Hierarchy}, journal = {Theoretical Computer Science A}, volume = {191}, number = {1--2}, pages = {97--115}, year = {1998}, url = {papers/DFR98_CircuitComplexity.pdf} }

@article{CaiChenDowneyFellows1997, title = {Advice Classes of Parameterized Tractability}, author = {Liming Cai and Jianer Chen and Rodney G. Downey and Michael R. Fellows}, journal = {Annals of Pure and Applied Logic}, year = {1997}, number = {1}, volume = {84}, pages = {119--138}, url = {papers/CCDF97_AdviceClasses.pdf} }

@article{CaiChenDowneyFellows1997b, title = {The Parameterized Complexity of Short Computation and Factorization}, author = {Liming Cai and Jianer Chen and Rodney G. Downey and Michael R. Fellows}, journal = {Archive for Mathematical Logic}, year = {1997}, volume = {36}, pages = {321--338}, abstract = {We study the parameterized complexity of: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word can be derived in a grammar in steps, or whether a permutation has a factorization of length over a given set of generators. We show hardness and completeness for these problems for various levels of the hierarchy.}, url = {papers/J41-shortcomp97.pdf} }

@incollection{DowneyFellowsRegan1997, title = {Descriptive Complexity and the {W} Hierarchy}, author = {R. Downey and M. Fellows and K. Regan}, booktitle = {Proof Complexity and Feasible Arithmetics}, editor = {P. Beame and S. Buss}, series = {AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science}, publisher = {American Mathematical Society}, year = {1997}, pages = {119-134}, url = {papers/C34-descriptive97.pdf} }

@inproceedings{DowneyFellowsTaylor1996, author = {Rod G. Downey and Michael R. Fellows and Udayan Taylor}, title = {The Parameterized Complexity of Relational Database Queries and an Improved Characterization of {W[1]}}, booktitle = {Combinatorics, Complexity, and Logic – Proceedings of DMTCS ’96}, year = {1996}, pages = {194--213}, publisher = {Springer-Verlag}, editor = {D. Bridges and C. Calude and J. Gibbons and S. Reeves and I. Witten}, url = {papers/C33.ps} }

@article{CesatiFellows1996, author = {M. Cesati and M. Fellows}, title = {Sparse parameterized problems}, journal = {Annals of Pure and Applied Logic}, year = {1996}, volume = {82}, pages = {1--15}, url = {papers/CF96_SparseParameterizedProbs..pdf} }

@article{AbrahamsonDowneyFellows1995b, author = {Karl Abrahamson and Rodney G. Downey and Michael R. Fellows}, title = {Fixed-Parameter Tractability and Completeness {IV}: On Completeness for {W[P]} and {PSPACE} Analogs}, journal = {Annals of Pure and Applied Logic}, volume = {73}, year = {1995}, pages = {235-276}, url = {papers/J31-fpt4-95.pdf} }

@article{DowneyFellows1995d, author = {Rodney G. Downey and Michael R. Fellows}, title = {Fixed-Parameter Tractability and Completeness {II}: On Completeness for {W[1]}}, journal = {Theoretical Computer Science}, volume = {141}, number = {1{\&}2}, year = {1995}, pages = {109-131}, url = {papers/DF95_FPTandCompletenessII.pdf} }

@inproceedings{DowneyFellows1993, author = {Rod Downey and Michael Fellows}, title = {Fixed-parameter tractability and completeness {III}: Some structural aspects of the {W} hierarchy}, booktitle = {Complexity Theory: Current Research -- Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity}, pages = {191--225}, year = {1993}, editor = {Klaus Ambos-Spies and Steven Homer and Uwe Sch{\"o}ning}, publisher = {Cambridge University Press}, address = {Cambridge} }

@article{CaiChenDowneyFellows1995b, title = {On the Structure of Parameterized Problems in {NP}}, author = {Liming Cai and Jianer Chen and Rodney Downey and Michael Fellows}, pages = {38--49}, journal = {Information and Computation}, year = {1995}, volume = {123}, number = {1}, abstract = {Fixed-parameter intractability of optimization problems in NP is studied based on computational models with limited nondeterminism. Strong evidence is shown that many NP optimization problems are not fixed-parameter tractable and that the fixed-parameter intractability hierarchy (the W-hierarchy) does not collapse.} }

@article{DowneyFellows1995f, author = {Rodney G. Downey and Michael R. Fellows}, title = {Fixed-Parameter Tractability and Completeness {I}: Basic Results}, journal = {SIAM Journal of Computing}, volume = {24}, number = {4}, year = {1995}, pages = {873-921}, url = {papers/DF95_FPTandCompletenessI.pdf} }

@inproceedings{CaiChenDowneyFellows1994, title = {On the Structure of Parameterized Problems in {NP}}, author = {Liming Cai and Jianer Chen and Rodney G. Downey and Michael R. Fellows}, booktitle = {Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science, STACS'94, Caen, France}, publisher = {Springer}, year = {1994}, volume = {775}, editor = {Patrice Enjalbert and Ernst W. Mayr and Klaus W. Wagner}, pages = {509--520}, series = {Lecture Notes in Computer Science} }

@inproceedings{AbrahamsonDowneyFellows1993b, author = {Karl A. Abrahamson and Rodney G. Downey and Michael R. Fellows}, title = {Fixed-parameter Intractability {II}}, booktitle = {Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93}, pages = {374--385}, year = {1993}, volume = {665}, series = {Lecture Notes in Computer Science}, editor = {P. Enjalbert and A. Finkel and K. W. Wagner}, publisher = {Springer-Verlag} }

@inproceedings{DowneyFellows1992, author = {Rod Downey and Michael Fellows}, title = {Fixed-parameter Intractability}, booktitle = {Proceedings of the Seventh Annual IEEE Conference on Structure in Complexity Theory}, pages = {36--49}, year = {1992} }

@article{DowneyFellows1992b, title = {Fixed-Parameter Tractability and Completeness}, author = {Rod Downey and Michael Fellows}, journal = {Congressus Numerantium}, year = {1992}, volume = {87}, pages = {161--178} }

@inproceedings{FellowsLangston1989b, author = {M. R. Fellows and M. Langston}, title = {An Analogue of the {M}yhill-{N}erode Theorem and Its Use in Computing Finite-Basis Characterizations}, booktitle = {Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS'89}, publisher = {IEEE Computer Society Press}, pages = {520-525}, year = {1989}, abstract = {A theorem that is a graph-theoretic analog of the Myhill-Nerode characterization of regular languages is proved. The theorem is used to establish that for many applications obstruction sets are computable by known algorithms. The focus is exclusively on what is computable (by a known algorithm) in principle, as opposed to what is computable in practice.}, url = {papers/C5-MyhillNerode-FOCS89.pdf} }

@inproceedings{AbrahamsonFellowsEllisMata1989, author = {K. R. Abrahamson and M. R. Fellows and J. A. Ellis and M. E. Mata}, title = {On the complexity of fixed parameter problems}, booktitle = {Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS'89}, publisher = {IEEE Computer Society Press}, pages = {210--215}, year = {1989}, abstract = {The paper addresses the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant α such that all problems in the family are solvable in time O(nα). The question is modeled by considering a class of polynomially indexed relations. The main results show that (1) this setting supports notions of completeness that can be used to explain the apparent hardness of certain problems with respect to fixed-parameter tractability, and (2) some natural problems are complete.}, url = {papers/C6-FOCS89.pdf} }

@techreport{DowneyFellowsMcCartin, author = {R. Downey and M.R. Fellows and C. Mccartin}, title = {Parameterized Approximation Problems} }

@inproceedings{FellowsGiannopoulosKnauerPaulRosamondWhitesidesYu2009, author = {M. Fellows and P. Giannopoulos and C. Knauer and C. Paul and F. Rosamond and S. Whitesides and N. Yu}, title = {On the Parameterized Complexity of the Discrete Milling Problem with Turn Costs}, journal = {Lecture Notes in Computer Science}, booktitle = {Proceedings of FST TCS'09}, publisher = {Springer-Verlag}, note = {To Appear}, year = {2009} }

@inproceedings{DomiFellowsRosamond2009, author = {M. Dom, M. Fellows and F. Rosamond}, title = {Parameterized Complexity of Stabbing Rectangles and Squares in the Plane}, journal = {Lecture Notes in Computer Science}, booktitle = {Proceedings of the 3rd Workshop on Algorithms and Computation, WALCOM'09}, volume = {5431}, pages = {298-309}, year = {2009}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, url = {papers/C90-rectstab_final.pdf} }

@article{FellowsKnauerNishimuraRagdeRosamondStegeThilikosWhitesides2008, author = {M. R. Fellows and C. Knauer and N. Nishimura and P. Ragde and F. Rosamond and U. Stege and D. Thilikos and S. Whitesides}, title = {Faster Fixed Parameter Tractable Algorithms for Matching and Packing Problems}, journal = {Algorithmica}, volume = {52}, number = {2}, year = {2008}, pages = {167--176}, publisher = {Springer-Verlag New York, Inc.}, url = {papers/J72-MatchingPacking-Algorithmica.pdf} }

@article{DujmovicFellowsKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2008, author = {Vida Dujmovic and Michael R. Fellows and Matthew Kitching and Giuseppe Liotta and Catherine McCartin and Naomi Nishimura and Prabhakar Ragde and Frances Rosamond and Sue Whitesides and David R. Wood}, title = {On the Parameterized Complexity of Layered Graph Drawing}, journal = {Algorithmica}, volume = {52}, number = {2}, year = {2008}, pages = {267--292}, publisher = {Springer-Verlag New York, Inc.}, url = {papers/J70-Algorithmica08.pdf} }

@article{DujmovicFellowsHallettKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2006, author = {Vida Dujmovic and Michael R. Fellows and Michael T. Hallett and Matthew Kitching and Giuseppe Liotta and Catherine McCartin and Naomi Nishimura and Prabhakar Ragde and Frances A. Rosamond and Matthew Suderman and Sue Whitesides and David R. Wood}, title = {A Fixed-Parameter Approach to 2-Layer Planarization}, journal = {Algorithmica}, volume = {45}, number = {2}, year = {2006}, pages = {159-182}, url = {papers/C64.pdf} }

@inproceedings{DujmovicFellowsHallettKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2001, author = {Vida Dujmovic and Michael R. Fellows and Michael T. Hallett and Matthew Kitching and Giuseppe Liotta and Catherine McCartin and Naomi Nishimura and Prabhakar Ragde and Frances A. Rosamond and Matthew Suderman and Sue Whitesides and David R. Wood}, title = {A Fixed-Parameter Approach to Two-Layer Planarization}, booktitle = {Proceedings of the 9th International Symposium on Graph Drawing GD'01}, pages = {1--15}, year = {2001}, volume = {2265}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, url = {papers/DFHKLMNRRSWW01_TwoLayerPlanarization.ps} }

@inproceedings{DujmovicFellowsHallettKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2001b, author = {V. Dujmovi{\'c} and M. Fellows and M. Hallett and M. Kitching and G.. Liotta and C. McCartin and N. Nishimura and P. Ragde and F. Rosamond and M. Suderman and S. Whitesides and D. R. Wood}, title = {On the Parameterized Complexity of Layered Graph Drawing}, journal = {Lecture Notes in Computer Science}, booktitle = {Proceedings of the 9th Annual European Symposium on Algorithms, ESA '01}, volume = {2161}, pages = {488--499}, year = {2001}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag} }

@article{BellFellowsWittenKoblitz2003, title = {Explaining Cryptographic Systems to the General Public}, author = {Tim Bell and Mike Fellows and Ian Witten and Neil Koblitz}, year = {2003}, journal = {Computers and Education}, volume = {40}, pages = {199--215} }

@article{DowneyFellowsVardyWhittle1999, author = {Rod G. Downey and Michael R. Fellows and Alexander Vardy and Geoff Whittle}, title = {The parametrized complexity of some fundamental problems in coding theory}, journal = {SIAM Journal of Computing}, pages = {545--570}, year = {1999}, number = {2}, volume = {29}, editor = {M. Yannakakis}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA}, abstract = {The parametrized complexity of a number of fundamental problems in the theory of linear codes and integer lattices is explored. Concerning codes, the main results are that MAXIMUM-LIKELIHOOD DECODING and WEIGHT DISTRUBUTION are hard for the parametrized complexity class W[1]. The NP-completeness of these two problems was established by Berlekamp, McEliece, and van Tilborg in 1978 using by means of a reduction from THREE-DIMENSIONAL MATCHING. On the other hand, our proof of hardness for W[1] is based on a parametric polynomial-time transformation from PERFECT CODE in graphs. An immediate consequence of our results is that bounded-distance decoding is likely to be hard for binary linear codes. Concerning lattices, we prove here for the first time that THETA SERIES is NP-complete and show that it is also hard for W[1]. Furthermore, we prove that the NEAREST VECTOR problem for integer lattices is hard for W[1]. These problems are the counterparts of WEIGHT DISTRUBUTION and MAXIMUM-LIKELIHOOD DECODING for lattices. Relations between all these problems and combinatorial problems in graphs are discussed.}, url = {papers/DFVW99_CodingTheory.pdf} }

@techreport{DowneyFellowsVardyWhittle1997, author = {Rod G. Downey and Michael R. Fellows and Alexander Vardy and Geoff Whittle}, title = {The parametrized complexity of some fundamental problems of Linear Codes and Integral Lattices}, year = {1997}, note = {Manuscript}, url = {papers/linearcodesIntegerLattices97.ps} }

@inproceedings{FellowsKoblizt1994, author = {Michael Fellows and Neal Koblitz}, booktitle = {Proceedings of the Second International Symposium on Finite Fields, Las Vegas, Nevada, August, 1993}, title = {Combinatorial cryptosystems galore!}, volume = {168}, publisher = {American Mathematical Society}, pages = {51--61}, year = {1994}, series = {Contemporary Mathematics}, url = {papers/C23-galore.pdf} }

@inproceedings{FellowsKoblitz1993, title = {Fixed-Parameter Complexity and Cryptography}, author = {Michael R. Fellows and Neal Koblitz}, booktitle = {Proceedings of 10th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC'93, San Juan de Puerto Rico, Puerto Rico}, publisher = {Springer}, year = {1993}, volume = {673}, editor = {G{\'e}rard D. Cohen and Teo Mora and Oscar Moreno}, pages = {121--131}, series = {Lecture Notes in Computer Science} }

@inproceedings{DowneyEvansFellows1993, title = {Parameterized Learning Complexity}, author = {Rodney G. Downey and Patricia A. Evans and Michael R. Fellows}, pages = {51--57}, booktitle = {Proceedings of the Sixth Annual {ACM} Conference on Computational Learning Theory}, year = {1993}, publisher = {ACM Press}, url = {papers/DEF93_LearningComplexity.pdf} }

@inproceedings{FellowsKoblitz1992, author = {Michael R. Fellows and Neal Koblitz}, title = {Self-witnessing polynomial-time complexity and prime factorization}, booktitle = {Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92}, pages = {107--110}, year = {1992}, publisher = {IEEE Computer Society Press}, url = {papers/C13-ccc92-primality.pdf} }

@article{FellowsKoblitz1992a, title = {Self-Witnessing Polynomial-Time Complexity and Prime Factorization}, author = {Michael R. Fellows and Neal Koblitz}, pages = {231--235}, journal = {Designs, Codes and Cryptography}, volume = {2}, number = {3}, year = {1992} }

@inproceedings{DinneenFellowsFaber1991, author = {M. J. Dinneen and M. R. Fellows and V. Faber}, title = {Algebraic Constructions of Efficient Broadcast Networks}, pages = {152--158}, editor = {Harold F. Mattson and Teo Mora and T. R. N. Rao}, booktitle = {Proceedings of Applied Algebra, Algebraic Algorithms and Error--Correcting Codes AAECC'91}, series = {LNCS}, volume = {539}, publisher = {Springer-Verlag}, address = {Berlin, Germany}, year = {1991} }

@article{BellFellowsKoblitzWitten2003, author = {T. Bell and M. Fellows and N. Koblitz and I. Witten}, title = {Explaining Cryptographic Ideas to the General Public}, journal = {Computers and Education}, volume = {40}, pages = {199—215}, year = {2003}, url = {papers/krypto.ps} }

@inproceedings{BellFellowsKoblitzWitten1999, author = {T. Bell and M. Fellows and N. Koblitz and I. Witten}, title = {Explaining Cryptographic Systems to the General Public}, booktitle = {Proceedings of the First IFIP World Conference on Information Security Education (WISE)}, publisher = {Stockholm University Report Series}, volume = {99-008}, editor = {L. Yngstgr\"{o}m and S. Fischer-H\"{u}bner}, pages = {221—233}, year = {1999} }

@article{CaseyFellows1997, author = {N. Casey and M. Fellows}, title = {Implementing the Standards: Let’s Focus on the First Four}, journal = {DIMACS Series: Discrete Mathematics in the Schools. How Can We Have an Impact?}, publisher = {AMS}, address = {Providence, RI, USA}, editor = {D. Franzblau and F. Roberts and J. Rosenstein}, year = {1997}, url = {papers/C30-StandardsFirst4-CF.pdf} }

@inproceedings{Fellows1996, author = {M. Fellows}, title = {The Heart of Puzzling: Mathematics and Computer Games}, booktitle = {Proceedings of the 1996 Computer Games Developers Conference}, publisher = {Miller Freeman}, pages = {109—120}, year = {1996}, url = {papers/C32-games.pdf} }

@article{FellowsHibnerKoblitz1994, author = {M.. Fellows and A. Hibner and N. Koblitz}, title = {Cultural Aspects of Mathematics Education Reform}, journal = {Notices of the American Mathematics Society}, volume = {41}, pages = {5—9}, year = {1994} }

@inproceedings{FellowsKoblitz1993b, author = {M. Fellows and N. Koblitz}, title = {Kid Krypto}, booktitle = {Proceedings of Crypto 1992}, publisher = {Springer-Verlag, New York, Inc.}, series = {Lecture Notes in Computer Science}, volume = {740}, pages = {371—389}, year = {1993}, url = {papers/C15-kidcrypto.pdf} }

@inproceedings{Fellows1993, author = {M. Fellows}, title = {Computer Science in the Elementary Schools}, booktitle = {Proceedings of the Mathematicians and Education Reform Workshop, Seattle, 1991}, editor = {N. Fisher and H. Keynes and P. Wagreich}, publisher = {Conference Board of the Mathematical Sciences}, series = {Issues in Mathematics Education}, volume = {3}, pages = {143 –163}, year = {1993}, url = {papers/C8.ps} }

@book{MegaMath_b, author = {Nancy Casey and Michael R. Fellows}, title = {This is Mega-Mathematics!}, publisher = {Los Alamos National Labs}, year = {1992}, note = {Available at http://www.c3.lanl.gov/~captors/mega-math. See also www.ccs3.lanl.gov/mega-math/write.html}, abstract = {A collection of classroom lessons in mathematics and computer science. Each lesson contains extensive background material that assumes that the topic of the lesson is new to the teacher. Topics include map coloring, graph theory, knot theory, finite state machines, algorithms, logic and infinity. }, url = {papers/MegaMath.pdf}, pages = {144} }

@article{FellowsLokshtanovMisraMnichRosamondSaurabh2009, title = {The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number}, author = {M. Fellows and D. Lokshtanov and N. Misra and M. Mnich and F. Rosamond and S. Saurabh}, journal = {Theory of Computing Systems}, year = {2009}, volume = {45}, pages = {822--848}, url = {papers/J76-TOCS-09.pdf} }

@inproceedings{FellowsGuoMoserNiedermeier2009b, title = {A Generalization of {N}emhauser and {T}rotter's Local Optimization Algorithm}, author = {Michael Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier}, booktitle = {Proceedings of STACS'09}, pages = {409--420}, year = {2009}, url = {papers/BC91-STACS-09.pdf} }

@inproceedings{FellowsMeisterRosamondSritharanTelle2008, title = {Leaf Powers and Their Properties: Using the Trees}, author = {Michael R. Fellows and Daniel Meister and Frances A. Rosamond and R. Sritharan and Jan Arne Telle}, booktitle = {Proceedings of Algorithms and Computation, 19th International Symposium, {ISAAC} 2008, Gold Coast, Australia}, publisher = {Springer-Verlag}, year = {2008}, volume = {5369}, editor = {Seok-Hee Hong and Hiroshi Nagamochi and Takuro Fukunaga}, pages = {402--413}, series = {Lecture Notes in Computer Science}, url = {papers/C89-ISAAC-08.pdf} }

@inproceedings{FellowsLokshtanovMisraRosamondSaurabh2008, title = {Graph Layout Problems Parameterized by Vertex Cover}, author = {Michael R. Fellows and Daniel Lokshtanov and Neeldhara Misra and Frances A. Rosamond and Saket Saurabh}, booktitle = {Proceedings of Algorithms and Computation, 19th International Symposium, {ISAAC} 2008, Gold Coast, Australia}, publisher = {Springer-Verlag}, year = {2008}, volume = {5369}, editor = {Seok-Hee Hong and Hiroshi Nagamochi and Takuro Fukunaga}, pages = {294--305}, series = {Lecture Notes in Computer Science}, url = {papers/C88-ISAAC-08.pdf} }

@inproceedings{BodlaenderFellowsHeggernesManciniPapadopoulosRosamond2008, title = {Clustering with Partial Information}, author = {Hans L. Bodlaender and Michael R. Fellows and Pinar Heggernes and Federico Mancini and Charis Papadopoulos and Frances A. Rosamond}, booktitle = {Proceedings of Mathematical Foundations of Computer Science, 33rd International Symposium, {MFCS} 2008, Torun, Poland}, publisher = {Springer-Verlag}, year = {2008}, volume = {5162}, editor = {Edward Ochmanski and Jerzy Tyszkiewicz}, pages = {144--155}, series = {Lecture Notes in Computer Science}, url = {papers/C86.pdf} }

@inproceedings{FellowsFernau2008b, title = {Facility Location Problems: {A} Parameterized View}, author = {Michael R. Fellows and Henning Fernau}, booktitle = {Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM'08}, publisher = {Springer-Verlag}, year = {2008}, volume = {5034}, editor = {Rudolf Fleischer and Jinhui Xu}, pages = {188--199}, series = {Lecture Notes in Computer Science}, url = {papers/C83-Facilities-AAIM08.pdf} }

@inproceedings{BodlaenderFellowsLangstonRaganRosamondWeyer2007, title = {Quadratic Kernelization for Convex Recoloring of Trees}, author = {Hans L. Bodlaender and Michael R. Fellows and Michael A. Langston and Mark A. Ragan and Frances A. Rosamond and Mark Weyer}, booktitle = {Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07}, publisher = {Springer-Verlag}, year = {2007}, volume = {4598}, editor = {Guohui Lin}, pages = {86--96}, series = {Lecture Notes in Computer Science}, url = {papers/C75-COCOON-07.pdf} }

@inproceedings{FellowsFominLokshtanovRosamondSaurabhSzeiderThomassen2007b, title = {On the Complexity of Some Colorful Problems Parameterized by Treewidth}, author = {Michael R. Fellows and Fedor V. Fomin and Daniel Lokshtanov and Frances A. Rosamond and Saket Saurabh and Stefan Szeider and Carsten Thomassen}, booktitle = {Proceedings of Combinatorial Optimization and Applications, COCOA'07}, publisher = {Springer-Verlag}, year = {2007}, volume = {4616}, editor = {Andreas W. M. Dress and Yinfeng Xu and Binhai Zhu}, pages = {366--377}, series = {Lecture Notes in Computer Science}, url = {papers/J79-submitted.pdf} }

@inproceedings{ChorFellowsRaganRazgonRosamondSnir2007, title = {Connected Coloring Completion for General Graphs: Algorithms and Complexity}, author = {Benny Chor and Michael R. Fellows and Mark A. Ragan and Igor Razgon and Frances A. Rosamond and Sagi Snir}, booktitle = {Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07}, publisher = {Springer-Verlag}, year = {2007}, volume = {4598}, editor = {Guohui Lin}, pages = {75--85}, series = {Lecture Notes in Computer Science}, url = {papers/C76-COCOON-07.pdf} }

@inproceedings{FellowsLangstonRosamondShaw2007a, title = {Efficient Parameterized Preprocessing for Cluster Editing}, author = {Michael R. Fellows and Michael A.. Langston and Frances A. Rosamond and Peter Shaw}, booktitle = {Proceedings of 16th International Symposium Fundamentals of Computation Theory FCT'07}, publisher = {Springer-Verlag}, year = {2007}, volume = {4639}, editor = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Zolt{\'a}n {\'E}sik}, pages = {312--321}, series = {Lecture Notes in Computer Science}, url = {papers/FLRS07_ClusterEdit.pdf} }

@article{CaiFellowsJuedesRosamond2007a, title = {The Complexity of Polynomial-Time Approximation}, author = {Liming Cai and Michael Fellows and David Juedes and Frances Rosamond}, year = {2007}, journal = {Theory of Computing Systems}, volume = {41}, number = {3}, pages = {459--477}, publisher = {Springer-Verlag New York, Inc.}, abstract = {We show that Planar TMIN, Planar TMAX and Planar MPSAT, parameterized by $k = 1/{$\epsilon$}$, are hard for W[1], and thus unlikely that they admit EPTASs. We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.}, url = {papers/J67-CFJR_jcss(old).pdf} }

@article{Abu-KhzamFellowsLangstonSuters2007, title = {Crown Structures for Vertex Cover Kernelization}, author = {Faisal N. Abu-Khzam and Michael R. Fellows and Michael A. Langston and W. Henry Suters}, publisher = {Springer-Verlag}, year = {2007}, abstract = {Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.}, journal = {Theory of Computing Systems}, number = {3}, volume = {41}, pages = {411--430}, url = {papers/J66-TOCS-crowns.pdf} }

@article{DehneFellowsLangstonRosamondStevens2007, title = {An $O(2^{O(k)}n^3)$ {FPT} Algorithm for the Undirected Feedback Vertex Set Problem}, author = {Frank Dehne and Michael Fellows and Michael Langston and Frances Rosamond and Kim Stevens}, publisher = {Springer-Verlag}, year = {2007}, abstract = {Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish {"}exponential optimality{"} for our algorithm.}, journal = {Theory of Computing Systems}, number = {3}, volume = {41}, pages = {479--492}, url = {papers/J65-TCS-07.pdf} }

@article{FellowsGrammNiedermeier2006b, author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier}, title = {On The Parameterized Intractability Of Motif Search Problems}, journal = {Combinatorica}, volume = {26}, number = {2}, year = {2006}, pages = {141--167}, publisher = {Springer-Verlag New York, Inc.}, url = {papers/FGN06_MotifSearch.pdf} }

@inproceedings{DehneFellowsFernauPrietoRosamond2006, title = {{NONBLOCKER}: Parameterized Algorithmics for Minimum Dominating Set}, author = {Frank Dehne and Michael R. Fellows and Henning Fernau and Elena Prieto and Frances A. Rosamond}, booktitle = {Proceedings of Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM'06}, publisher = {Springer-Verlag}, year = {2006}, volume = {3831}, editor = {Jir{\'i} Wiedermann and Gerard Tel and Jaroslav Pokorn{\'y} and M{\'a}ria Bielikov{\'a} and Julius Stuller}, pages = {237--245}, series = {Lecture Notes in Computer Science}, url = {papers/DFFPR06_Nonblocker.pdf} }

@inproceedings{FellowsRosamondRoticsSzeider2006, title = {Clique-Width Minimization is {NP}-Hard}, author = {Michael R. Fellows and Frances A. Rosamond and Udi Rotics and Stefan Szeider}, booktitle = {Proceedings of the 38th Annual Symposium on Theory of Computing, ACM'06}, publisher = {ACM}, year = {2006}, editor = {Jon M. Kleinberg}, pages = {354--362}, url = {papers/FRRS06_CliquewidthNPhard.pdf} }

@inproceedings{BurrageEstivill-CastroFellowsLangstonMacRosamond2006, title = {The Undirected Feedback Vertex Set Problem Has a Poly($k$) Kernel}, author = {Kevin Burrage and Vladimir Estivill-Castro and Michael R. Fellows and Michael A. Langston and Shev Mac and Frances A. Rosamond}, booktitle = {Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06}, publisher = {Springer-Verlag}, year = {2006}, volume = {4169}, editor = {Hans L. Bodlaender and Michael A. Langston}, pages = {192--202}, series = {Lecture Notes in Computer Science}, url = {papers/C68-IWPEC-06.pdf} }

@inproceedings{BodlaenderFellowsLangstonRaganRosamondWeyer2006, title = {Kernelization for Convex Recoloring}, author = {Hans L. Bodlaender and Michael R. Fellows and Michael A. Langston and Mark A. Ragan and Frances A. Rosamond and Mark Weyer}, booktitle = {Proceedings of Algorithms and Complexity in Durham, {AC}i{D}'06}, publisher = {King's College, London}, year = {2006}, volume = {7}, editor = {Hajo Broersma and Stefan S. Dantchev and Matthew Johnson 0002 and Stefan Szeider}, pages = {23--36}, series = {Texts in Algorithmics}, note = {Accepted to Algorithmica}, url = {papers/J79-submitted.pdf} }

@article{AlberFanFellowsFernauNiedermeierRosamondStege2005, author = {Jochen Alber and Hongbing Fan and Michael R. Fellows and Henning Fernau and Rolf Niedermeier and Fran Rosamond and Ulrike Stege}, title = {A Refined Search Tree Technique for Dominating Set on Planar Graphs}, journal = {Journal of Computer and System Sciences}, volume = {71}, number = {4}, year = {2005}, pages = {385--405}, publisher = {Academic Press, Inc.}, url = {papers/AFFFNRS05_PlanarDS.pdf} }

@inproceedings{DehneFellowsLangstonRosamondStevens2005, title = {An {O}(2$^{O(k)}$n$^{3}$) {FPT} Algorithm for the Undirected Feedback Vertex Set Problem}, author = {Frank K. H. A. Dehne and Michael R. Fellows and Michael A. Langston and Frances A. Rosamond and Kim Stevens}, booktitle = {Proceedings of Computing and Combinatorics, 11th Annual International Conference, {COCOON}'05}, publisher = {Springer-Verlag}, year = {2005}, volume = {3595}, editor = {Lusheng Wang}, pages = {859--869}, series = {Lecture Notes in Computer Science}, url = {papers/C64.pdf} }

@inproceedings{Estivill-CastroFellowsLangstonRosamond2005, title = {Fixed-Parameter Tractability is Polynomial-Time Extremal Structure Theory {I}: The Case of Max Leaf}, author = {Vladimir Estivill-Castro and Michael R. Fellows and Michael A. Langston and Frances A. Rosamond}, booktitle = {Proceedings of Algorithms and Complexity in Durham, {AC}i{D} 2005}, publisher = {King's College, London}, year = {2005}, volume = {4}, editor = {Hajo Broersma and Matthew Johnson 0002 and Stefan Szeider}, pages = {1--41}, series = {Texts in Algorithmics}, url = {papers/C65-maxleaf.pdf} }

@article{AlberFellowsNiedermeier2004, author = {J. Alber and M. R. Fellows and R. Niedermeier}, title = {Polynomial-Time Data Reduction for Dominating Set}, abstract = {We demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a problem kernel of linear size, achieved by two easy-to-implement reduction rules. Our first experiments indicate practical potential of these rules. Thus, this work seems to open up a new and way of coping with one of the most important problems in graph theory and combinatorial optimization.}, journal = {Journal of the ACM}, volume = {51}, number = {3}, year = {2004}, pages = {363--384}, url = {papers/J58-AlFeNi02.pdf} }

@article{EllisFanFellows2004, author = {J. Ellis and H. Fan and M. Fellows}, title = {The Dominating Set Problem is Fixed Parameter Tractable for Graphs of Bounded Genus}, journal = {Journal of Algorithms}, pages = {152--168}, year = {2004}, number = {2}, volume = {52}, abstract = {We describe an algorithm for the dominating set problem with time complexity $O((4g+40)^k n^2)$ for graphs of bounded genus $g \ge 1$, where $k$ is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous $O(8^k n^2)$ result for planar graphs.. Our method is a refinement of the earlier techniques.}, editor = {Zvi Galil and David S. Johnson and Donald E. Knuth}, publisher = {Elsevier B.V.} }

@inproceedings{Abu-KhzamCollinsFellowsLangstonSutersSymons2004, author = {Faisal N. Abu-Khzam and Rebecca L. Collins and Michael R. Fellows and Michael A. Langston and W. Henry Suters and Christopher T. Symons}, title = {Kernelization Algorithms for the {V}ertex {C}over Problem: Theory and Experiments}, pages = {62--69}, editor = {Lars Arge and Guiseppe F. Italiano and Robert Sedgewick}, booktitle = {Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics {ALENEX}'04}, series = {Siam Proceedings Series}, publisher = {Society of Industrial and Applied Mathematics}, year = {2004} }

@inproceedings{FelllowsKnauerNishimuraRagdeRosamondStegeThilikosWhitesides2004, author = {M. R. Fellows and C. Knauer and N. Nishimura and P. Ragde and F. A. Rosamond and U. Stege and D. M. Thilikos and S. Whitesides}, title = {Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems}, pages = {311--322}, editor = {S. Albers and T. Radzik}, booktitle = {Proceedings of 12th Annual European Symposium on Algorithms {ESA}'04}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {3221}, year = {2004}, url = {papers/C61.pdf} }

@inproceedings{FellowsHeggernesRosamondSloperTelle2004, title = {Finding $k$ Disjoint Triangles in an Arbitrary Graph}, author = {Mike Fellows and Pinar Heggernes and Frances A. Rosamond and Christian Sloper and Jan Arne Telle}, booktitle = {Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,{WG}'04}, publisher = {Springer-Verlag}, year = {2004}, volume = {3353}, editor = {Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel}, pages = {235--244}, series = {Lecture Notes in Computer Science}, url = {papers/C62-wg2004.pdf} }

@inproceedings{ChorFellowsJuedes2004, title = {Linear Kernels in Linear Time, or How to Save $k$ Colors in {O}(n$^2$) Steps}, author = {Benny Chor and Mike Fellows and David W. Juedes}, booktitle = {Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,{WG}'04}, publisher = {Springer-Verlag}, year = {2004}, volume = {3353}, editor = {Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel}, pages = {257--269}, series = {Lecture Notes in Computer Science}, url = {papers/CFJ04_LinearKernels.pdf} }

@article{FellowsHallettStege2003a, author = {M. R. Fellows and M. Hallett and U. Stege}, title = {Analogs and Duals of the {MAST} Problem for Sequences \& Trees}, journal = {Journal of Algorithms}, volume = {49}, year = {2003}, pages = {192 -- 216}, url = {papers/J54-MAST.pdf} }

@article{DowneyEstivill-CastroFellowsPrietoRosamond2003b, title = {Cutting Up is Hard to Do: the Parameterized Complexity of {k}-Cut and Related Problems}, author = {Rodney G. Downey and Vladimir Estivill-Castro and Michael R. Fellows and Elena Prieto and Frances A. Rosamond}, journal = {Electronic Notes in Theoretical Computer Science}, year = {2003}, volume = {78}, pages = {205--218}, url = {papers/DEPR03_kcut.pdf} }

@inproceedings{Fellows2003a, author = {Michael R. Fellows}, title = {Blow-ups, win/win's, and crown rules: Some new directions in {FPT}}, booktitle = {Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'03}, pages = {1--12}, year = {2003}, volume = {2880}, series = {LNCS}, abstract = {This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.}, editor = {Hans L. Bodlaender}, publisher = {Springer-Verlag}, url = {papers/C52-WG03.pdf} }

@inproceedings{DehneFellowsRosamond2003, author = {Frank Dehne and Michael R. Fellows and Frances A. Rosamond}, title = {An {FPT} algorithm for set splitting}, booktitle = {Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'03}, pages = {180--191}, year = {2003}, volume = {2880}, series = {Lecture Notes in Computer Science}, abstract = {An FPT algorithm with a running time of $O(n ^4 + 2^{O(k)} n^{2.5})$ is described for the Set Splitting problem, parameterized by the number $k$ of sets to be split. It is also shown that there can be no FPT algorithm for this problem with a running time of the form $2^ {o(k)} n^c$ unless the satisfiability of $n$-variable 3SAT instances can be decided in time $2^{o(n)}$.}, editor = {Hans L. Bodlaender}, publisher = {Springer-Verlag}, url = {papers/C53-WG-2003.pdf} }

@inproceedings{BodlaenderFellowsThilikos2003, author = {H. L. Bodlaender and M. R. Fellows and D. M. Thilikos}, title = {Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms}, booktitle = {Proceedings of Mathematical Foundations of Computer Science MFCS'03}, year = {2003}, pages = {239--248}, editor = {B. Rovan and P. Vojt{\'a}s}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {2747}, url = {papers/C55-nondeterminism-MFCS03.pdf.pdf} }

@inproceedings{AlberFellowsNiedermeier2002, title = {Efficient Data Reduction for {DOMINATING} {SET}: {A} Linear Problem Kernel for the Planar Case}, author = {Jochen Alber and Michael R. Fellows and Rolf Niedermeier}, booktitle = {Proceedings of 8th Scandinavian Workshop on Algorithm Theory {SWAT}'02}, publisher = {Springer}, year = {2002}, volume = {2368}, editor = {Martti Penttonen and Erik Meineche Schmidt}, pages = {150--159}, series = {Lecture Notes in Computer Science}, url = {papers/C50-swat2002.pdf} }

@inproceedings{EllisFanFellows2002, author = {J. Ellis and H. Fan and M.~R. Fellows}, title = {The Dominating Set Problem is Fixed Parameter Tractable for Graphs of Bounded Genus}, booktitle = {Proceedings of SWAT 2002: Scandinavian Workshop on Algorithm Theory}, year = {2002}, volume = {2368}, editor = {M. Penttonen and E. Meineche Schmidt}, series = {LNCS}, pages = {180--189}, publisher = {Springer}, url = {papers/C51.pdf} }

@inproceedings{AlberFanFellowsFernauNiedermeierRosamondStege2001, title = {A Refined Search Tree Technique for {DOMINATING} {SET} on Planar Graphs}, author = {Jochen Alber and Hongbing Fan and Michael R. Fellows and Henning Fernau and Rolf Niedermeier and Frances A. Rosamond and Ulrike Stege}, abstract = {We establish refined search tree techniques for the parameterized Dominating Set problem on planar graphs. We prove an intricate branching theorem based on the Euler formula. In addition, we give a family of example graphs showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final algorithm is easy to implement; its analysis, however, is involved.}, booktitle = {Proceedings of 26th International Symposium Mathematical Foundations of Computer Science, MFCS'01}, publisher = {Springer-Verlag}, year = {2001}, volume = {2136}, editor = {Jiri Sgall and Ales Pultr and Petr Kolman}, pages = {111--122}, series = {Lecture Notes in Computer Science}, url = {papers/AFFFNRS01_PlanarDomSet.ps} }

@article{DowneyFellowsRaman2000, author = {Rodney G. Downey and Michael R. Fellows and Venkatesh Raman}, title = {The Complexity of Irredundant Sets Parameterized by Size}, journal = {Discrete Applied Mathematics}, volume = {100}, number = {3}, year = {2000}, pages = {155-167}, url = {papers/DFR00_IrredundanceSets.pdf} }

@article{BodlaenderFellowsHallettWarehamWarnow2000a, author = {Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett and H. Todd Wareham and Tandy J. Warnow}, title = {The Hardness of Perfect Phylogeny, Feasible Register Assignment and other problems on Thin Colored Graphs}, journal = {Theoretical Computer Science A}, abstract = {We consider the complexity of Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has a uniform upper bound on the tree or pathwidth of the graphs in {"}yes{"}-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for W [t] for all t 2 N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.}, volume = {244}, number = {1--2}, pages = {167--188}, year = {2000}, url = {papers/BFHWW00_PhylogenyThinColoredGraphs.pdf} }

@inproceedings{FellowsMcCartinRosamondStege2000a, title = {Coordinatized Kernels and Catalytic Reductions: An Improved {FPT} Algorithm for Max Leaf Spanning Tree and Other Problems}, author = {Michael R. Fellows and Catherine McCartin and Frances A. Rosamond and Ulrike Stege}, booktitle = {Proceedings of Foundations of Software Technology and Theoretical Computer Science, 20th Conference, {FST} {TCS} '00}, publisher = {Springer-Verlag}, year = {2000}, volume = {1974}, editor = {Sanjiv Kapoor and Sanjiva Prasad}, pages = {240--251}, series = {Lecture Notes in Computer Science}, url = {papers/C40-KernelsCatalytic-2000.pdf} }

@inproceedings{FellowsHallettKorostenskyStege1998a, author = {M. Fellows and M. T. Hallett and C. Korostensky and U. Stege}, title = {Analogs and Duals of the {MAST} Problem for Sequences and Trees}, abstract = {Two natural kinds of problems about {"}structured collections of symbols{"} can be generally refered to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as leaf-labels and a subobject is defined by label-respecting hereditary topological containment, both of these problems are NP-complete, as are the analogous problems for sequences (the well-known Longest Common Subsequence and Shortest Common Supersequence problems). However, when the trees are restricted by allowing each symbol to occur as a leaf-label at most once (which we call a phylogenetic tree or p-tree), then the Largest Common Subobject problem, better known as the Maximum Agreement Subtree (MAST) problem, is solvable in polynomial time. We explore the complexity of the basic subobject and superobject problems for sequences and binary trees.}, booktitle = {Proceedings of the 6th Annual European Symposium on Algorithms}, editor = {G. Bilardi and G. F. Italiano and A. Pietracaprina and G. Pu cci}, series = {Lecture Notes in Computer Science}, number = {1461}, publisher = {Springer-Verlag, Berlin}, year = {1998}, pages = {103--114}, url = {papers/J54-MAST-early.pdf} }

@article{BalasubramanianFellowsRaman1998, author = {Balasubramanian and Fellows and Raman}, title = {An Improved Fixed-Parameter Algorithm for Vertex Cover}, journal = {IPL: Information Processing Letters}, volume = {65}, number = {3}, year = {1998}, pages = {163--168}, url = {papers/BFR98_VC.pdf} }

@article{DowneyFellows1998a, author = {Rodney G. Downey and Michael R. Fellows}, title = {Threshold Dominating Sets and an Improved Characterization of ${W}[2]$}, journal = {Theoretical Computer Science}, pages = {123--140}, year = {1998}, number = {1-2}, volume = {209}, publisher = {Elsevier Science Publishers B.V. (North Holland)}, url = {papers/J46-wstar2.pdf} }

@article{AlonFellowsHare1996, author = {Noga Alon and Michael R. Fellows and Donovan R. Hare}, title = {Vertex Transversals that Dominate}, journal = {Journal of Graph Theory}, pages = {21--32}, year = {1996}, number = {1}, volume = {21}, publisher = {John Wiley \& Sons}, url = {papers/J36-JGT96.pdf} }

@article{CattellDinneenFellows1996c, author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows}, title = {A Simple Linear-Time Algorithm for finding Path-Decompositions of Small Width}, journal = {Information Processing Letters}, pages = {197--203}, year = {1996}, number = {4}, volume = {57}, publisher = {North-Holland Publishing Company}, abstract = {We describe a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^{k})$. This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.}, url = {papers/CDF96_PathDecompOfSmallWidth.pdf} }

@inproceedings{DowneyFellowsTaylor1996b, author = {Rod G. Downey and Michael R. Fellows and Udayan Taylor}, title = {The Parameterized Complexity of Relational Database Queries and an Improved Characterization of {W[1]}}, booktitle = {Proceedings of Combinatorics, Complexity, and Logic, DMTCS'96}, year = {1996}, pages = {194--213}, publisher = {Springer-Verlag}, editor = {D. Bridges and C. Calude and J. Gibbons and S. Reeves and I. Witten}, url = {papers/C33-relationaldatabase.ps} }

@article{FellowsFrickeHedetniemiJacobs1994, author = {Michael Fellows and Gerd Fricke and Stephen Hedetniemi and David Jacobs}, title = {The Private Neighbor Cube}, journal = {SIAM Journal on Discrete Mathematics}, volume = {7}, number = {1}, pages = {41--47}, year = {1994} }

@inproceedings{BodlaenderFellowsHallett1994a, author = {Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett}, title = {Beyond ${NP}$-completeness for problems of bounded width: Hardness for the ${W}$ hierarchy}, booktitle = {Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94}, pages = {449--458}, year = {1994}, publisher = {ACM Press}, address = {New York}, url = {papers/BFH94_BoundedWidth..pdf} }

@article{FellowsLangston1992b, author = {Michael R. Fellows and Michael A. Langston}, title = {On Well-Partial-Order Theory and Its Application to Combinatorial Problems of {VLSI} Design}, journal = {SIAM Journal on Discrete Mathematics}, volume = {5}, number = {1}, pages = {117--126}, year = {1992} }

@article{AbelloFellowsStillwell1991, author = {Abello and Fellows and Stillwell}, title = {On the Complexity and Combinatorics of Covering Finite Complexes}, journal = {AJC: Australasian Journal of Combinatorics}, volume = {4}, year = {1991}, pages = {103--112} }

@article{FellowsKaschube1991, author = {Michael R. Fellows and P. A. Kaschube}, title = {Searching for $K_{3,3}$ in Linear Time}, journal = {Linear and Multilinear Algebra}, volume = {29}, number = {3}, pages = {279--290}, year = {1991} }

@article{FellowsHoover1991, author = {M. R. Fellows and M. Hoover}, title = {Perfect Domination}, journal = {AJC: Australasian Journal of Combinatorics}, volume = {3}, year = {1991}, pages = {141--150} }

@article{BarefootClarkDouthettEntringerFellows1991a, author = {C. A. Barefoot and L. H. Clark and J. Douthett and R. C. Entringer and M. R. Fellows}, title = {Cycles of Length 0 Modulo 3 in Graphs}, journal = {Annals of Discrete Mathematics}, note = {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}, year = {1991}, pages = {87--101} }

@article{FellowsWojciechowski1989, author = {M. R. Fellows and J. M. Wojciechowski}, title = {Counting Spanning Trees in Directed Regular Multigraphs}, journal = {Journal of the Franklin Institute}, volume = {326}, year = {1989}, pages = {889--896} }

@article{BrownFellowsLangston1989a, author = {D. J. Brown and M. R. Fellows and M. A. Langston}, title = {Polynomial-Time Self-Reducibility: Theoretical Motivations and Practical Results}, journal = {International Journal of Computer Mathematics}, volume = {31}, year = {1989}, pages = {1--9} }

@article{FellowsStueckle1989a, author = {M. R. Fellows and S. Stueckle}, title = {The Immersion Order, Forbidden Subgraphs and the Complexity of Network Integrity}, journal = {Journal of Combinatorial Mathematics and Combinatorial Computing}, volume = {6}, year = {1989}, pages = {23--32} }

@article{FellowsFriesenLangston1988, author = {Michael R. Fellows and Donald K. Friesen and Michael A. Langston}, title = {On Finding Optimal and Near-Optimal Lineal Spanning Trees}, journal = {Algorithmica}, volume = {3}, number = {4}, pages = {549--560}, year = {1988} }

@article{FellowsHooverHarary1988, title = {On the Galactic Number of a Hypercube}, journal = {Mathematical and Computer Modelling}, volume = {11}, pages = {212 - 215}, year = {1988}, author = {Michael Fellows and Mark Hoover and Frank Harary}, abstract = {A galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determining the galactic number of a graph is shown to be NP-complete.} }

@inproceedings{BryantFellowsKinnersleyLangston1987a, author = {R. L. Bryant and Michael R. Fellows and N. G. Kinnersley and Michael A. Langston}, title = {On Finding Obstruction Sets and Polynomial-Time Algorithms for Gate Matrix Layout}, booktitle = {Proceedings of the 25th Allerton Conference on Communication, Control and Computing}, pages = {397--398}, year = {1987} }

@article{FellowsHicklingSyslo1987, title = {A Topological Parameterization and Hard Graph Problems}, journal = {Congressus Numerantium}, volume = {59}, pages = {69--78}, year = {1987}, author = {M. Fellows and F. Hickling and M. Syslo} }

@article{ClarkEntringerFellows1987, title = {Computational Complexity of Integrity}, journal = {Journal of Combinatorial Mathematics and Combinatorial Computing}, volume = {2}, pages = {179--191}, year = {1987}, author = {L. H. Clark and R. C. Entringer and M. Fellows} }

@article{BodlaenderDowneyFellowsHermelin2010, title = {On Problems without Polynomial Kernels}, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Danny Hermelin}, journal = {Journal of Computer and System Sciences}, note = {To Appear}, year = {2010} }

@inproceedings{FellowsHromkovicRosamondSteinova2009b, title = {Fixed-Parameter Tractability, Relative Kernelization and the Effectivization of Structural Connections}, author = {M. Fellows and J. Hromkovic and F. Rosamond and M. Steinova}, booktitle = {Proceedings of CiE'09}, publisher = {Springer-Verlag}, year = {2009}, note = {To Appear}, series = {Lecture Notes in Computer Science}, url = {papers/C102-Cie09abstract.pdf} }

@inproceedings{Fellows2009b, title = {The Complexity Ecology of Parameters: Some New Developments and Research Directions}, author = {Michael R. Fellows}, booktitle = {Proceedings of IWOCA'09}, publisher = {Springer-Verlag}, year = {2009}, note = {To Appear}, series = {Lecture Notes in Computer Science}, url = {papers/C101-IWOCA-09.pdf} }

@article{FellowsLokshtanovMisraMnichRosamondSaurabhb2009, author = {M.R. Fellows and D. Lokshtanov and N. Misra and M. Mnich and F. Rosamond and S. Saurabh}, title = {The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number}, pages = {822-848}, journal = {Theory of Computing Systems}, volume = {45}, year = {2009}, url = {papers/J76-TOCS-09.pdf} }

@article{BodlaenderFellowsLangstonRaganRosamondWeyer2009, author = {H. Bodlaender and M.R. Fellows and M. Langston and M. Ragan and F. Rosamond and M. Weyer}, title = {Quadratic Kernelization for Convex Recoloring of Trees}, journal = {Algorithmica}, note = {Accepted to Algorithmica}, year = {2009}, url = {papers/J79-submitted.pdf} }

@inproceedings{BodlaenderDowneyFellowsHermelin2008b, title = {On Problems without Polynomial Kernels}, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Danny Hermelin}, booktitle = {Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games}, publisher = {Springer-Verlag}, year = {2008}, volume = {5125}, editor = {Luca Aceto and Ivan Damg{\aa}rd and Leslie Ann Goldberg and Magn{\'u}s M. Halld{\'o}rsson and Anna Ing{\'o}lfsd{\'o}ttir and Igor Walukiewicz}, pages = {563--574}, series = {Lecture Notes in Computer Science}, url = {papers/C85-ICALP-08.pdf} }

@article{Abu-KhzamFellowsLangstonSuters2007b, title = {Crown Structures for Vertex Cover Kernelization}, author = {Faisal N. Abu-Khzam and Michael R. Fellows and Michael A. Langston and W. Henry Suters}, publisher = {Springer-Verlag}, year = {2007}, abstract = {Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are compared both theoretically and experimentally with each other and with older kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.}, journal = {Theory of Computing Systems}, number = {3}, volume = {41}, pages = {411--431}, url = {papers/J66-TOCS-crowns.pdf} }

@inproceedings{FellowsLangstonRosamondShaw2007b, title = {Efficient Parameterized Preprocessing for Cluster Editing}, author = {Michael R. Fellows and Michael A.. Langston and Frances A. Rosamond and Peter Shaw}, booktitle = {Proceedings of Fundamentals of Computation Theory, 16th International Symposium, {FCT}'07}, publisher = {Springer-Verlag}, year = {2007}, volume = {4639}, editor = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Zolt{\'a}n {\'E}sik}, pages = {312--321}, series = {Lecture Notes in Computer Science}, url = {papers/C78-FCT07.pdf} }

@inproceedings{BodlaenderFellowsLangstonRaganRosamondWeyer2007b, title = {Quadratic Kernelization for Convex Recoloring of Trees}, author = {Hans L. Bodlaender and Michael R. Fellows and Michael A. Langston and Mark A. Ragan and Frances A. Rosamond and Mark Weyer}, booktitle = {Proceedings of Computing and Combinatorics, 13th Annual International Conference, {COCOON}'07}, publisher = {Springer-Verlag}, year = {2007}, volume = {4598}, editor = {Guohui Lin}, pages = {86--96}, series = {Lecture Notes in Computer Science}, url = {papers/C75-COCOON-07.pdf} }

@inproceedings{BurrageEstivill-CastroFellowsLangstonMacRosamond2006b, title = {The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel}, author = {Kevin Burrage and Vladimir Estivill-Castro and Michael R. Fellows and Michael A. Langston and Shev Mac and Frances A. Rosamond}, booktitle = {Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06}, publisher = {Springer-Verlag}, year = {2006}, volume = {4169}, editor = {Hans L. Bodlaender and Michael A. Langston}, pages = {192--202}, series = {Lecture Notes in Computer Science}, url = {papers/C68-IWPEC-06.pdf} }

@inproceedings{Fellows2006b, author = {M. Fellows}, title = {The Lost Continent of Polynomial Time}, booktitle = {Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {4169}, pages = {276 – 277}, year = {2006}, url = {papers/C70-LostContinent.pdf} }

@inproceedings{Estivill-CastroFellowsLangstonRosamond2005b, title = {Fixed-Parameter Tractability is Polynomial-Time Extremal Structure Theory {I}: The Case of Max Leaf}, author = {Vladimir Estivill-Castro and Michael R. Fellows and Michael A. Langston and Frances A. Rosamond}, booktitle = {Algorithms and Complexity in Durham 2005 - Proceedings of the First {AC}i{D}}, publisher = {King's College, London}, year = {2005}, volume = {4}, editor = {Hajo Broersma and Matthew Johnson 0002 and Stefan Szeider}, pages = {1--41}, series = {Texts in Algorithmics}, url = {papers/C65-maxleaf.pdf} }

@article{AlberFellowsNiedermeier2004b, author = {J. Alber and M. R. Fellows and R. Niedermeier}, title = {Polynomial-Time Data Reduction for Dominating Set}, abstract = {We prove that Dominating Set restricted to planar graphs has a kernel of linear size, achieved by two easy-to-implement reduction rules. First experiments indicate the practical potential of these rules. Thus, this work seems to open up a new way of coping with one of the most important problems in graph theory and combinatorial optimization.}, journal = {Journal of the ACM}, volume = {51}, number = {3}, year = {2004}, pages = {363--384}, url = {papers/J58-AlFeNi02.pdf} }

@inproceedings{Abu-KhzamCollinsFellowsLangstonSutersSymons2004b, author = {Faisal N. Abu-Khzam and Rebecca L. Collins and Michael R. Fellows and Michael A. Langston and W. Henry Suters and Christopher T. Symons}, title = {Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments}, pages = {62--69}, editor = {Lars Arge and Guiseppe F. Italiano and Robert Sedgewick}, booktitle = {Proceedings of the sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04}, series = {Siam Proceedings Series}, publisher = {Society of Industrial and Applied Mathematics}, year = {2004} }

@inproceedings{ChorFellowsJuedes2004b, title = {Linear Kernels in Linear Time, or How to Save $k$ Colors in {O}(n$^2$) Steps}, author = {Benny Chor and Mike Fellows and David W. Juedes}, booktitle = {Graph-Theoretic Concepts in Computer Science, 30th International Workshop WG'04}, publisher = {Springer-Verlag}, year = {2004}, volume = {3353}, editor = {Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel}, pages = {257--269}, series = {Lecture Notes in Computer Science}, url = {papers/CFJ04_LinearKernels.pdf} }

@inproceedings{AlberFellowsNiedermeier2002b, title = {Efficient Data Reduction for {DOMINATING} {SET}: {A} Linear Problem Kernel for the Planar Case}, author = {Jochen Alber and Michael R. Fellows and Rolf Niedermeier}, booktitle = {Proceedings of the 8th Scandinavian Workshop on Algorithm Theory SWAT'02}, publisher = {Springer-Verlag}, year = {2002}, volume = {2368}, editor = {Martti Penttonen and Erik Meineche Schmidt}, pages = {150--159}, series = {Lecture Notes in Computer Science}, url = {papers/C50-swat2002.pdf} }

@inproceedings{FellowsMcCartinRosamondStege2000, title = {Coordinatized Kernels and Catalytic Reductions: An Improved {FPT} Algorithm for Max Leaf Spanning Tree and Other Problems}, author = {Michael R. Fellows and Catherine McCartin and Frances A. Rosamond and Ulrike Stege}, booktitle = {Proceedings Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS'00}, publisher = {Springer-Verlag}, year = {2000}, volume = {1974}, editor = {Sanjiv Kapoor and Sanjiva Prasad}, pages = {240--251}, series = {Lecture Notes in Computer Science}, url = {papers/C40-KernelsCatalytic-2000.pdf} }

@inproceedings{BodlaenderFellowsHallett1994b, author = {Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett}, title = {Beyond ${NP}$-Completeness for problems of Bounded Width: Hardness for the ${W}$ Hierarchy}, booktitle = {Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94}, pages = {449--458}, year = {1994}, publisher = {ACM Press}, url = {papers/BFH94_BoundedWidth.pdf} }

@article{CaiFellowsJuedesRosamond2007b, title = {On The Efficiency of Polynomial-Time Approximation}, author = {Liming Cai and Michael Fellows and David Juedes and Frances Rosamond}, year = {2007}, journal = {Theory of Computing Systems}, volume = {41}, number = {3}, pages = {459--477}, publisher = {Springer-Verlag New York, Inc.}, address = {Secaucus, NJ, USA}, abstract = {We offer a number of results concerning the problems Planar TMIN, Planar TMAX and Planar MPSAT defined by Khanna and Motwani: (1) We show that each of these problems of approximation, naturally parameterized by $k = 1/{$\epsilon$}$, is hard for W[1], and thus unlikely that they admit EPTASs. (2) We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.}, url = {papers/J67-CFJR_jcss(old).pdf} }

@inproceedings{DowneyFellowsMcCartin2006, title = {Parameterized Approximation Problems}, author = {Rodney G. Downey and Michael R. Fellows and Catherine McCartin}, booktitle = {Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06}, publisher = {Springer}, year = {2006}, volume = {4169}, editor = {Hans L. Bodlaender and Michael A. Langston}, pages = {121--129}, series = {Lecture Notes in Computer Science} }

@article{FellowsSzeiderWrightson2006, author = {M. Fellows and S. Szeider and G. Wrightson}, title = {On Finding Short Resolution Refutations and Small Unsatisfiable Subsets}, pages = {351--359}, journal = {Theoretical Computer Science}, volume = {351}, year = {2006}, abstract = {We consider the parameterized problems of whether a given set of clauses can be refuted within $k$ resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most $k$. We show that both problems are complete for W[1]. Our results remain true if restricted to 3-SAT formulas and/or to various restricted versions of resolution including tree-like resolution, input resolution, and read-once resolution. Applying a metatheorem of Frick and Grohe, we show that restricted to classes of locally bounded treewidth the considered problems are FPT. Hence, the problems are fixed-parameter tractable for planar CNF formulas and CNF formulas of bounded genus, $k$-SAT formulas with bounded number of occurrences per variable, and CNF formulas of bounded treewidth. }, url = {papers/J62-ShortResolution-TCS06.pdf} }

@inproceedings{FellowsSzeiderWrightson2004, author = {M. Fellows and S. Szeider and G. Wrightson}, title = {On Finding Short Resolution Refutations and Small Unsatisfiable Subsets}, booktitle = {Proceedings of the First International Workshop on Parameterized and Exact Computation IWPEC'04}, series = {Lecture Notes in Computer Science }, publisher = {Springer-Verlag }, volume = {3162}, pages = {223--234}, year = {2004}, url = {papers/C60-szeider-wrightson.pdf} }

@article{DowneyFellows2001b, author = {R.. Downey and M. Fellows}, title = {Index Sets and Parametric Reductions}, pages = {329--348}, journal = {Archive for Mathematical Logic}, volume = {40}, year = {2001}, number = {5}, url = {papers/J51-IndexSets01.pdf} }

@inproceedings{FellowsDowneyKapronHallettWareham1994, author = {M. Fellows and R. Downey and B. Kapron and M. Hallett and H. T. Wareham}, title = {The Parameterized Complexity of Some Problems in Logic and Linguistics}, booktitle = {Proceedings of Symposium on Logical Foundations of Computer Science (LFCS)}, publisher = { Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = {813}, year = {1994}, pages = {89 -- 100 } }

@article{FellowsMcCartin2003, author = {M. Fellows and C. McCartin}, title = {On the Parameterized Complexity of Minimizing Tardy Tasks}, journal = {Theoretical Computer Science A}, volume = {298}, year = {2003}, pages = {317--324} }

@article{BodlaenderFellows1995, author = {H. Bodlaender and M. Fellows}, title = {On the Complexity of $k$-Processor Scheduling}, journal = {Operations Research Letters}, volume = {18}, pages = {93 – 98}, year = {1995}, url = {papers/BF95_ProcessorScheduling.pdf} }

@article{FellowsLangston1988c, author = {M. Fellows and M. A. Langston}, title = {Processor Utilization in a Linearly Connected Parallel Processing System}, journal = {IEEE Transactions on Computers}, volume = {37}, year = {1988}, pages = {594 – 603} }

@inproceedings{FellowsFlumHermelinMullerRosamond2007b, author = {Michael Fellows and J{\"o}rg Flum and Danny Hermelin and Moritz M{\"u}ller and Frances Rosamond}, title = {Parameterized Complexity via Combinatorial Circuits}, booktitle = {Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop}, pages = {55--67}, year = {2007}, editor = {Hajo Broersma and Stefan Dantchev and Matthew Johnson and Stefan Szeider}, volume = {9}, series = {Texts in Algorithmics}, publisher = {College Publications London}, url = {papers/C80-ACiD07-Circuits.pdf} }

@article{FellowsHellSeyffarth1998, author = {M. Fellows and P. Hell and K. Seyffarth}, title = {Constructions of Dense Planar Networks}, journal = {Networks}, volume = {32}, year = {1998}, pages = {275-281} }

@article{AlonFellowsHare1996a, author = {N. Alon and M. Fellows and D. O. Hare}, title = {Vertex Transversals That Dominate}, journal = {Journal of Graph Theory}, volume = {21}, year = {1996}, pages = {21--32}, url = {papers/J36-JGT96.pdf} }

@article{FellowsHellSeyffarth1995, author = {M. Fellows and P. Hell and K. Seyffarth}, title = {Large Planar Graphs with Given Diameter and Maximum Degree}, journal = {Discrete Applied Math}, volume = {61}, year = {1995}, pages = {133--153} }

@article{CampbellCarlssonDinneenFaberFellowsLangstonMooreMullhauptSexton1992, author = {L. Campbell and G. E. Carlsson and M. J. Dinneen and V. Faber and M. Fellows and M. A. Langston and J. W. Moore and A. P. Mullhaupt and H. B. Sexton}, title = {Small Diameter Symmetric Networks From Linear Groups}, journal = {IEEE Transactions on Computers}, volume = {40}, year = {1992}, pages = {218-220} }

@article{BarefootClarkDouthettEntringerFellows1991b, author = {C. A. Barefoot and L. H. Clark and J. Douthett and R.. C. Entringer and M. R. Fellows}, title = {Cycles of Length 0 Modulo 3 in Graphs}, journal = {Annals of Discrete Mathematics}, note = {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}, year = {1991}, pages = {87--101} }

@inproceedings{DinneenFaberFellows1991, author = {M. Dinneen and V. Faber and M. Fellows}, title = {Algebraic Constructions of Efficient Broadcast Networks}, editor = {H. F. Mattson and T. Mora and T.R.N. Rao}, booktitle = {Proceedings of the Ninth International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC'91)}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, volume = {539}, year = {1991}, pages = {152--158} }

@article{FellowsKleitman1990, author = {M. Fellows and D. J. Kleitman}, title = {Transversals of Vertex Partitions in Graphs}, journal = { SIAM Journal of Discrete Mathematics}, volume = {3}, year = {1990}, pages = {206-215} }

@article{FellowsKleitman1989, author = {M. Fellows and D. J. Kleitman}, title = {Radius and Diameter in Manhattan Lattices}, journal = { Discrete Mathematics}, volume = {73}, year = {1989}, pages = {119--125} }

@inproceedings{BodlaenderEvansFellows1996, title = {Finite-State Computability of Annotations of Strings and Trees}, author = {Hans L. Bodlaender and Patricia A. Evans and Michael R. Fellows}, booktitle = {Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM 2006}, editor = {Daniel S. Hirschberg and Eugene W. Myers}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {1075}, year = {1996}, pages = {384-391} }

@inproceedings{AbrahamsonFellows1993b, title = {Finite Automata, Bounded Treewidth and Well-Quasiordering}, author = {Karl R. Abrahamson and Michael R. Fellows}, publisher = {American Mathematical Society }, editor = {N. Robertson and P. Seymour }, booktitle = {Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991}, series = {Contemporary Mathematics}, volume = {147}, year = {1993}, pages = {539--564} }

@inproceedings{FellowsLangston1989c, author = {M. Fellows and M. Langston}, title = {An analogue of the {M}yhill-{N}erode theorem and its use in computing finite-basis characterizations}, booktitle = {Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89 (Research Triangle Park, NC)}, pages = {520--525}, year = {1989}, publisher = {IEEE Computer Society Press} }

@article{BodlaenderFellowsThilikos2009, author = {H. Bodlaender and M. Fellows and D. Thilikos}, title = {Derivation of Algorithms for Cutwidth and Related Graph Layout Parameters}, journal = {Journal of Computer and System Sciences}, volume = {75}, page = {231--244}, year = {2009}, abstract = {This paper shows algorithms for graph parameters that ask for a linear ordering of the vertices of the graph. Constructive linear time algorithms for the fixed parameter versions of the problems have been published for cutwidth, pathwidth, and directed or weighted variants of these and other problems. However, the algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for variants.} }

@article{FellowsRosamondRoticsSzeider2009, author = {M. Fellows and F. Rosamond and U. Rotics and S. Szeider}, title = {Cliquewidth is {NP}-{C}omplete}, journal = {SIAM Journal on Discrete Mathematics (SIDMA) }, volume = {23}, number = {2}, page = {909--939}, year = {2009}, abstract = {Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g.., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. We show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless P=NP. We also show that, given a graph G and an integer k, deciding whether the clique-width of G is at most k is NP-complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s}, note = {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)}, url = {papers/C73-CliquewidthRevision1Aug05.pdf}, url = {papers/C73-CliquewidthIIRevisionAug05.pdf} }

@inproceedings{AbrahamsonFellowsWilson1992, title = {Parallel Self-Reducibility}, author = {Karl R. Abrahamson and Michael R. Fellows and Christopher B. Wilson}, booktitle = {Proceedings of Computing and Information ICCI'92, Fourth International Conference on Computing and Information}, publisher = {IEEE Computer Society}, year = {1992}, editor = {Waldemar W. Koczkodaj and Peter E. Lauer and Anestis A. Toptsis}, pages = {67--70} }

@inproceedings{FellowsKoblitz1992b, author = {Michael R. Fellows and Neal Koblitz}, title = {Self-Witnessing Polynomial-time Complexity and Certificates for Primality}, booktitle = {Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92}, pages = {107--110}, year = {1992}, publisher = {IEEE Computer Society Press}, url = {papers/C13-ccc92-primality.pdf} }

@article{AbrahamsonFellowsLangstonMoret1991, author = {Karl Abrahamson and Michael R. Fellows and Michael A. Langston and Bernard M. E. Moret}, title = {Constructive Complexity}, abstract = {Robinson and Seymour have provided tools for classifying decision problems as solvable in polynomial time that are powerful and widely applicable, yet inherently non-constructive. These developments challenge the view that equates tractability with polynomial time solvability, since the existence of an inaccessible algorithm is of very little help in solving a problem. In this paper, we attempt to provide the foundations for a constructive theory of complexity, in which membership of a problem in some complexity class indeed implies that we can find out how to solve that problem within the stated bounds. Our approach is based on relations, rather than on sets; we make much use of self-reducibility and oracle machines, both conventional and {"}blind,{"}. }, journal = {Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science}, pages = {3--16}, year = {1991}, volume = {34}, publisher = {North-Holland Publishing Company} }

@article{FellowsLangston1991, title = {Fast Search Algorithms for Layout Permutation Problems}, journal = {Integration, the VLSI Journal}, volume = {12}, number = {3}, pages = {321 - 337}, year = {1991}, author = {Michael R. Fellows and Michael A. Langston} }

@inproceedings{FellowsLangston1989d, author = {Michael R. Fellows and Michael A. Langston}, title = {On Search, Decision and the Efficiency of Polynomial-time Algorithms}, booktitle = {Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC'89}, pages = {501--512}, year = {1989}, publisher = {ACM Press}, organization = {ACM SIGACT}, url = {papers/FL89_Search,Decision,Efficiency.pdf} }

@article{FellowsLangston1987a, author = {Michael R. Fellows and Michael A. Langston}, title = {Nonconstructive advances in polynomial-time complexity}, journal = {Information Processing Letters}, pages = {157--162}, year = {1987}, number = {3}, volume = {26}, publisher = {North-Holland Publishing Company} }

@inproceedings{FellowsLangston1988d, author = {Michael R. Fellows and Michael A. Langston}, title = {Fast self-reduction algorithms for combinatorial problems of {VLSI} design}, booktitle = {Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece}, pages = {278--287}, year = {1988}, volume = {319}, series = {LNCS}, editor = {J. H. Reif}, publisher = {Springer-Verlag} }

@inproceedings{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009c, author = {Michael R. Fellows and Fedor V. Fomin and Daniel Lokshtanov and Elena Losievskaja and Frances A. Rosamond and Saket Saurabh}, title = {Distortion Is Fixed Parameter Tractable}, booktitle = {Proceedings of ICALP 2009 (Track A)}, year = {2009}, pages = {463-474}, url = {papers/C96.pdf} }

@techreport{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009d, title = {Parameterized Low-distortion Embeddings - Graph Metrics into Lines and Trees}, author = {Michael Fellows and Fedor Fomin and Daniel Lokshtanov and Elena Losievskaja and Frances A. Rosamond and Saket Saurabh}, note = {Manuscript}, year = {2009}, abstract = {We describe algorithms for finding a low distortion non-contracting embedding of $M$ into line and tree metrics. We give an $O(nd^4(2d+1)^{2d})$ time algorithm that for an unweighted graph metric $M$ and integer $d$ either constructs an embedding of $M$ into the line with distortion at most $d$, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is $O(n(dW)^4(2d+1)^{2dW})$ where $W$ is the largest edge weight of the input graph. We also show that deciding whether a weighted graph metric $M(G)$ with maximum weight $W < |V(G)|$ can be embedded into the line with distortion at most $d$ is NP-Complete for every fixed rational $d \geq 2$. This rules out any possibility of an algorithm with running time $O((nW)^{h(d)})$ where $h$ is a function of $d$ alone. We generalize the result on embedding into the line by proving that for any tree $T$ with maximum degree $\Delta$, embedding of $M$ into a shortest path metric of $T$ is FPT, parameterized by $(\Delta,d)$.} }

@inproceedings{FellowsGrammNiedermeier2002a, author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier}, title = {On the parameterized intractability of Closest Substring and related problems}, abstract = {We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard with respect to the number $k$ of input strings (even over a binary alphabet). This problem is therefore unlikely to be solvable in time $O(f(k)n)$ for any function $f$ and constant $c$ independent of $k$. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NP-complete and both possess polynomial time approximation schemes. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our main W[1]-hardness result generalizes to Consensus Patterns, a problem of significance in computational biology.}, booktitle = {Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS'02}, pages = {262--273}, year = {2002}, volume = {2285}, series = {LNCS}, editor = {Helmut Alt and Afonso Ferreira}, publisher = {Springer-Verlag}, url = {papers/C48-stacs02-substrings.pdf} }

@inproceedings{BodlaenderEvansFellows1996a, title = {Finite-State Computability of Annotations of Strings and Trees}, author = {Hans L. Bodlaender and Patricia A. Evans and Michael R. Fellows}, booktitle = {Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM'96}, editor = {Daniel S. Hirschberg and Eugene W. Myers}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {1075}, year = {1996}, pages = {384-391} }

@article{BodlaenderDowneyFellowsWareham1995a, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Harold T. Wareham}, title = {The Parameterized Complexity of Sequence Alignment and Consensus}, journal = {Theoretical Computer Science}, volume = {147}, number = {1{\&}2}, year = {1995}, pages = {31-54}, url = {papers/BDFW95_SeqAlignment.pdf} }

@article{BodlaenderDowneyFellowsHallettWareham1995c, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Michael T. Hallett and Harold T. Wareham}, title = {Parameterized complexity analysis in computational biology}, journal = {Computer Applications in the Biosciences}, volume = {11}, number = {1}, year = {1995}, pages = {49-57}, url = {papers/BDFHW95CompBio.pdf} }

@inproceedings{BodlaenderDowneyFellowsWareham1994a, title = {The Parameterized Complexity of Sequence Alignment and Consensus}, author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Harold T. Wareham}, booktitle = {Combinatorial Pattern Matching, 5th Annual Symposium, CPM'94}, publisher = {Springer}, year = {1994}, volume = {807}, editor = {Maxime Crochemore and Dan Gusfield}, pages = {15--30}, series = {Lecture Notes in Computer Science} }