BibTeX

My publications, in BibTeX format

@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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/papers/C77-ICALP-07.pdf}
}

@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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/papers/J54-MAST.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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/papers/ C79-COCOA-07.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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/papers/C55-nondeterminism-MFCS03.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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/papers/C73-CliquewidthRevision1Aug05.pdf},
url = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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 = {http://www.mrfellows.net/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}
}