Michael Fellows

    School of Electrical Engineering and Computer Science
    The University of Newcastle
    Calaghan NSW 2308
    Australia

    email: mfellows@cs.newcastle.edu.au
    phone: 61-2-4921-5291
                                                                              fax: 61-2-4921-6929

I am the Professor of Computer Science at the University of Newcastle.

Research Interests

The Design and Analysis of Algorithms; Computational Complexity Theory; Parameterized Complexity and Parameterized Algorithms; Computational Biology; Computer Games and Mathematical Sciences Education .

Courses (2003)

User Interface Design, SENG 3300

Publications

Books and Monographs

Parameterized Complexity, 530 pp., Springer-Verlag, 1999, Rodney G. Downey and Michael R. Fellows.
Computer Science Unplugged ... offline activities and games for all ages, 231 pp., 1996, Tim Bell, Ian Witten and Mike Fellows.
This is Mega-Mathematics!, 134 pp., 1992, Nancy Casey and Mike Fellows.

Survey Articles and Chapters in Books

New Directions and New Challenges in Algorithms and Complexity, Parameterized. To appear in: Proceedings of WADS'03, Springer-Verlag, Lecture Notes in Computer Science (2003).
Parameterized Complexity: The Main Ideas and Connections to Practical Computing. In: Experimental Algorithmics, Springer-Verlag, Lecture Notes in Computer Science, 2547 (2002), 51--77.
Parameterized Complexity: A Survey , Proc. CATS 2002, Computing: The Australasian Theory Symposium, James Harland (ed.), Elsevier, Electronic Notes in Computer Science, (2002), 1--17.
Parameterized Complexity: Main Ideas, Connections to Heuristics and Research Frontiers, Proc. ISAAC 2001, Springer-Verlag, Lecture Notes in Computer Science, 2223 (2001), 291--307.
Some New Developments in Parameterized Complexity, Proc. 12th Australasian Workshop on Combinatorial Algorithms, ed. Edy Tri Baskoro (2001), 43--44.
Parameterized Complexity: New Developments and Research Frontiers, Proc. New Zealand Mathematical Sciences Research Institute Summer Workshop, Kaikoura, 2000, Aspects of Complexity, R. Downey and D. Hirschfeldt (eds.), de Gruyter (2001), 51--72 (notes on featured short course).
Parameterized Complexity: The View from Mars, The Complexity Column, SIGACT News, Fall 2000.
Parameterized Complexity After (Almost) 10 Years: Review and Open Questions, in: Combinatorics, Computation and Logic, DMTCS'99 and CATS'99, Australian Computer Science Communications 21, Springer-Verlag Singapore (1999), 1--33, M. Fellows and R. Downey.
Parameterized Complexity: A Framework for Systematically Confronting Computational Intractability, in: Contemporary Trends in Discrete Mathematics, (R. Graham, J. Kratochvil, J. Nesetril and F. Roberts, eds.), Proc. DIMACS-DIMATIA Workshop, Prague, 1997, AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49 (1999), 49-99, R. Downey, M. Fellows and U. Stege.
Parameterized Computational Feasibility, Feasible Mathematics II, P. Clote and J. Remmel (eds.), Birkhauser Boston (1995), 219--244, M. Fellows and R. Downey.

Some Recent Manuscripts

Analogs and Duals of the MAST Problem for Sequences and Trees, to appear in: Journal of Algorithms, M. Fellows, M. Hallett and U. Stege.
An FPT Algorithm for Set Splitting, to appear in: Proceedings WG 2003, Springer-Verlag, Lecture Notes in Computer Science, F. Dehne, M. Fellows and F. Rosamond.
Starting with Nondeterminism: the Systematic Derivation of Linear-Time Graph Layout Algorithms, to appear in: Proceedings MFCS 2003, Springer-Verlag, Lecture Notes in Computer Science, H. Bodlaender, M. Fellows and D. Thilikos.
Refined Search Tree Technique for Dominating Sets on Planar Graphs, submitted to: Journal of Computer and Systems Science, J. Alber, H. Fan, M. Fellows, H. Fernau, R. Niedermeier, F. Rosamond and U. Stege.
On Efficient PTAS for Problems on Planar Structures, submitted to: Journal of Computer and Systems Science, L. Cai, M. Fellows, D. Juedes and F. Rosamond.
Parameterized Intractability of Motif Search Problems, submitted to: Algorithmica, M. Fellows, J. Gramm and R. Niedermeier.
Algorithms for Layout Problems of Small Pathwidth Made Easier, submitted to: Journal of Algorithms, H. Bodlaender, M. Fellows and D. Thilikos.
The Parameterized Complexity of Finding Irrelevant Features and Related Data Mining Problems, C. Cotta, M. Fellows, P. Moscato and F. Rosamond.
Polynomial-Time Data Reduction for Dominating Set, submitted to: Algorithmica, J. Alber, M. Fellows and R. Niedermeier.
The Dominating Set Problem is Fixed Parameter Tractable on Graphs of Bounded Genus, submitted to: Journal of the ACM, J. Ellis, H. Fan and M. Fellows.
Improving the Diameter of a Planar Graph, to appear in: Discrete Applied Mathematics, M.R. Fellows and I.J. Dejter.

Journal Papers

Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems, Electronic Notes in Theoretical Computer Science 78 (2003), 205--218, R. Downey, V. Estivill-Castro, M. Fellows, E. Prieto-Rodriguez and F. Rosamond.
Explaining Cryptographic Ideas to the General Public, Computers and Education 40 (2003), 199--215, T. Bell, H. Thimbleby, M. Fellows, I. Witten, N. Koblitz and M. Powell.
On the Parameterized Complexity of Minimizing Tardy Tasks, Theoretical Computer Science A 298 (2003), M. Fellows and C. McCartin.
Forbidden Minors to Graphs with Small Feedback Sets, Discrete Mathematics 230 (2001), 215--252, K. Cattell, M. Dinneen and M. Fellows.
Index Sets and Parametric Reductions, Archive for Mathematical Logic 40 (2001), 329--348, M.R. Fellows and R.G. Downey.
The Hardness of Perfect Phylogeny, Feasible Register Assignment and Other Problems on Thin Colored Graphs, Theoretical Computer Science A 244 (2000), 167-188, H. Bodlaender, M. Fellows, M. Hallett, H.T. Wareham and T. Warnow.
The Complexity of Irredundant Sets Parameterized by Size, Discrete Applied Mathematics 100 (2000), 155-167, R. Downey, M. Fellows and V. Raman.
On Computing Graph Minor Obstruction Sets, Theoretical Computer Science A 233 (2000), 107--127, K. Cattell, M.J. Dinneen, R.G. Downey, M.R. Fellows and M.A. Langston.
The Parameterized Complexity of Some Fundamental Problems in Coding Theory, SIAM J. Computing 29 (1999), 545-570, R. Downey, M. Fellows, A. Vardy and G. Whittle.
Threshold Dominating Sets and An Improved Characterization of W[2], Theoretical Computer Science A 209 (1998), 123--140, R. Downey and M. Fellows.
Constructions of Dense Planar Networks, Networks 32 (1998), 275-281, M. Fellows, P. Hell and K. Seyffarth.
An Improved Fixed-Parameter Algorithm for Vertex Cover, Information Processing Letters 65 (1998), 163--168, R. Balasubramanian, M. Fellows and V. Raman.
Parameterized Circuit Complexity and the W Hierarchy , Theoretical Computer Science A 191 (1998), 91--115, R.G. Downey, M.R. Fellows and K. W. Regan.
A Note on the Computability of Obstruction Sets for Monadic Second Order Ideals, Journal of Universal Computer Science 3 (1997), 1194--1198, with B. Courcelle and R. Downey.
The Parameterized Complexity of Short Computation and Factorization, Proceedings of the Sacks Symposium, in: Archive for Mathematical Logic 36 (1997), 321--338, L. Cai, J. Chen, R. Downey and M. Fellows.
Advice Classes of Parameterized Tractability, Annals of Pure and Applied Logic 84 (1997), 119--138, L. Cai, J. Chen and R. Downey and M. Fellows.
Approaches to Detection of Distantly Related Proteins by Database Searches, BioTechniques 21 (1996), 1118--1125, K. Cattell, R. Olafson, B. Koop, I. Bailey, R.W. Olafson, M. Fellows and C. Upton.
Sparse Parameterized Problems, Annals of Pure and Applied Logic 82 (1996), 1--15, M. Cesati and M. Fellows.
A Simple Linear Time Algorithm for Finding Path Decompositions of Small Width, Information Processing Letters 57 (1996), 197--203, K. Cattell, M.J. Dinneen and M. Fellows.
Vertex Transversals That Dominate, Journal of Graph Theory 21 (1996), 21--32, N. Alon, M. Fellows and D.O. Hare.
On the Complexity of k-Processor Scheduling, Operations Research Letters 18 (1995), 93--98, H. Bodlaender and M. Fellows.
On the Parameterized Complexity of Problems in NP, Information and Computation 123 (1995), 38--49. L. Cai, J. Chen, R. Downey and M. Fellows.
Parameterized Complexity Analysis in Computational Biology, Computer Applications in the Biosciences 11 (1995), 49--57, H. Bodlaender, R. Downey, M. Fellows, M. Hallett, and H.T. Wareham.
The Parameterized Complexity of the Longest Common Subsequence Problem, Theoretical Computer Science A 147 (1995), 31--54, H. Bodlaender, R. Downey, M. Fellows and H.T. Wareham.
Fixed Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogs, Annals of Pure and Applied Logic 73 (1995), 235--276, K. Abrahamson, R. Downey and M. Fellows.
Fixed-Parameter Tractability and Completeness II: Completeness for W[1], Theoretical Computer Science A 141 (1995), 109--131, R. Downey and M. Fellows.
Fixed-Parameter Tractability and Completeness I: Basic Theory, SIAM J. Computing 24 (1995), 873--921, R. Downey and M. Fellows.
Large Planar Graphs with Given Diameter and Maximum Degree, Discrete Applied Math. 61 (1995), 133--153, M. Fellows, P. Hell and K. Seyffarth.
The Complexity of Induced Minors and Related Problems, Algorithmica 13 (1995), 266--282, M. Fellows, J. Kratochvil, M. Middendorf and F. Pfeiffer.
On Search, Decision and the Efficiency of Polynomial-Time Algorithms, Journal of Computer and Systems Science 49 (1994), 769--779, M. R. Fellows and M. A. Langston.
Cultural Aspects of Mathematics Education Reform, Notices of the American Mathematics Society 41 (1994), 5--9, M. Fellows, A. Hibner and N. Koblitz.
The Private Neighborhood Cube, SIAM J. Discrete Mathematics 7 (1994), 41-47, M. Fellows, G. Fricke, S. Hedetniemi and D. Jacobs.
Self-Witnessing Polynomial-Time Complexity and Certificates for Primality, Designs, Codes and Cryptography 2 (1992), 231-235, M. Felows and N. Koblitz.
Fixed-Parameter Tractability and Completeness, Congessus Numerantium 87 (1992), 161-178, R. Downey and M. Fellows.
Small Diameter Symmetric Networks From Linear Groups, IEEE Transactions on Computers 40 (1992), 218-220, L. Campbell, G. E. Carlsson, M. J. Dinneen, V. Faber, M. Fellows, M. A. Langston, J. W. Moore, A. P. Mullhaupt and H. B. Sexton.
On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design, SIAM J. Discrete Math. 5 (1992), 117-126, M. R. Fellows and M. A. Langston.
On the Complexity and Combinatorics of Covering Finite Complexes, Australasian J. Combinatorics 4 (1991), 103-112, J. Abello, M. Fellows and J. Stillwell.
Constructive Complexity, Discrete Applied Math. 34 (1991), 3-16, with K. Abrahamson, M. A. Langston and B. Moret. (At the special invitation of the editor-in-chief, this was published also in the book series Annals of Discrete Mathematics, in: Combinatorics and Theoretical Computer Science, R. Simion, ed., North-Holland, 1992, pp. 3--16.)
Cycles of Length 0 Modulo 3 in Graphs, Annals of Discrete Math. (1991), 87-101, C. A. Barefoot, L. H. Clark, J. Douthett, M. Fellows and R. C. Entringer.
Fast Search Algorithms for Graph Layout Permutation Problems, Integration, the VLSI Journal 12 (1991), 321-337, M. Fellows and M. Langston.
Perfect Domination, Australasian J. Combinatorics 3 (1991), 141-150, M. Fellows and M. Hoover.
Searching for K(3,3) in Linear Time, Linear and Multilinear Algebra 29 (1991), 279-290, M. Fellows and P. Kaschube.
Transversals of Vertex Partitions in Graphs, SIAM J. Discrete Math. 3 (1990), 206-215.
The Immersion Order, Forbidden Subgraphs and the Complexity of Network Integrity, Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32, M. Fellows and S. Stueckle.
Counting Spanning Trees in Directed Regular Multigraphs, Journal of the Franklin Institute 326 (1989), 889-896, J. M. Wojciechowski and M. R. Fellows.
The Robertson-Seymour Theorems: A Survey of Applications, Contemporary Mathematics 89 (1989), 1--18.
Polynomial-Time Self-Reducibility: Theoretical Motivations and Practical Results, International Journal of Computer Mathematics 31 (1989), 1--9, D.J. Brown, M.R. Fellows and M.A. Langston.
On the Galactic Number of a Hypercube, Mathematical and Computer Modelling 11 (1988), 212--215, M. Fellows, F. Harary and M. Hoover.
Radius and Diameter in Manhattan Lattices, Discrete Mathematics 73 (1989), 119--125, D. J. Kleitman and M. R. Fellows.
On Finding Optimal and Near-Optimal Lineal Spanning Trees, Algorithmica 3 (1988), 549--560, with D. K. Friesen and M. A. Langston.
Processor Utilization in a Linearly Connected Parallel Processing System, IEEE Transactions on Computers 37 (1988), 594--603, M.R. Fellows and M.A. Langston.
Nonconstructive Proofs of Polynomial-Time Complexity, Information Processing Letters 26 (1987/88), 157--162, M.R. Fellows and M.A. Langston.
Computational Complexity of Integrity, Journal of Combinatorial Mathematics and Combinatorial Computing 2 (1987), 179--191, L.H. Clark, R.C. Entringer and M.R. Fellows.
A Topological Parameterization and Hard Graph Problems, Congressus Numerantium 59 (1987), 69--78, M. Fellows, F. Hickling and M. Syslo.

Conference Papers not covered by Journal Articles or Manuscripts in Review

On the Parameterized Complexity of Layered Graph Drawing, Proc. 9th Annual European Symposium on Algorithms (ESA 2001), Springer-Verlag, Lecture Notes in Computer Science 2161 (2001), 488--499, V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides and D. Wood.
A Fixed-Parameter Tractability Approach to Two-Layered Graph Drawing, Proc. 9th International Symposium on Graph Drawing (GD 2001), Springer-Verlag, Lecture Notes in Computer Science 2265 (2001), 1--15, V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides and D. Wood.
Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems, Proceedings of FST-TCS 2000, Springer-Verlag, Lecture Notes in Computer Science 1974 (2000), 240--251, with C. McCartin, F. Rosamond and U. Stege.
On the Multiple Gene Duplication Problem, Proceedings Ninth International Symposium on Algorithms and Computation -- ISAAC'98, Springer-Verlag, Lecture Notes in Computer Science 1533 (1998), 347--356, M. Fellows, M. Hallett and U. Stege.
Descriptive Complexity and the W Hierarchy, in: Proof Complexity and Feasible Arithmetics (P. Beame and S. Buss, Eds.) AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society (1997), 119-134, R. Downey, M. Fellows and K. Regan.
The Parameterized Complexity of Relational Database Queries and An Improved Characterization of W[1], in: Combinatorics, Complexity and Logic, Proceedings of DMTCS '96, (D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds.) Springer-Verlag (1996), 194-213, R. Downey, M. Fellows and U. Taylor.
The Heart of Puzzling: Mathematics and Computer Games, Proceedings of the 1996 Computer Games Developers Conference, Miller Freeman (1996), 109--120.
Finite-State Computability of Annotations of Strings and Trees, Proceedings Seventh Symposium on Combinatorial Pattern Matching (CPM '96), Springer-Verlag, Lecture Notes in Computer Science 1075 (1996), 384--391, H. Bodlaender, P. Evans and M. Fellows.
Let's Focus on the First Four, in: Discrete Mathematics in the Schools: How Can We Have an Impact? (D. Franzblau, F. Roberts and J. Rosenstein, eds.) DIMACS/AMS proceedings series, 1997, N. Casey and M. Fellows.
Combinatorial Cryptosystems Galore! Proceedings of the Second International Symposium on Finite Fields, Las Vegas, Nevada, August, 1993, Contemporary Mathematics 168 (1994), 51--61, with N. Koblitz.
DNA Physical Mapping: Three Ways Difficult, in Algorithms --- ESA '93, (Proceedings of the First European Symposium on Algorithms), Springer-Verlag, Berlin, Lecture Notes in Computer Science 726 (1993), 157--168, with M.T. Hallett and H.T. Wareham.
Parameterized Learning Complexity, Proceedings of the Sixth ACM Workshop on Computational Learning Theory (COLT'93), 51--57, with R.G. Downey and P.A. Evans.
Fixed-Parameter Complexity and Cryptography, Proceedings of the Tenth International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC'93), Springer-Verlag, Berlin, Lecture Notes in Computer Science 673 (1993), 121--131, M. Fellows and N. Koblitz.
Kid Krypto, Proceedings of Crypto '92, Springer-Verlag, Lecture Notes in Computer Science 740 (1993), 371-389, M. Fellows and N. Koblitz.
Parallel Self-Reducibility, Proc. 4th International Conference on Computing and Information, IEEE Computer Society Press (1992), 67--70, K. Abrahamson, M. Fellows and C. Wilson.
Finite Automata, Bounded Treewidth and Well-Quasiordering, in: N. Robertson and P. Seymour (editors), Graph Structure Theory: Proceedings of the Joint Summer Research Conference on Graph Minors, Seattle, June, 1991, American Mathematical Society, Contemporary Mathematics 147 (1993), 539--564, K. Abrahamson and M. Fellows.
Computer Science in the Elementary Schools, Mathematicians and Education Reform Workshop, Seattle, 1991. Proceedings published as: Mathematicians and Education Reform 1990--1991, N. Fisher, H. Keynes and P. Wagreich, eds., Conference Board of the Mathematical Sciences, Issues in Mathematics Education 3 (1993), 143--163.
Fast Self-Reduction Algorithms for Combinatorial Problems of VLSI Design, Proceedings Third International Workshop on Parallel Computation and VLSI Theory, Springer-Verlag, Lecture Notes in Computer Science 319 (1988), 278--287, M. Fellows and M. Langston.