Michael Fellows - Publications#

Mike's research contributions have been internationally recognized. Mike has published over 200 articles in high-quality peer reviewed journals (such as J. of ACM, TOCT, SIAM J. Computing, J. Comput. Syst. Sci., Algorithmica, Discrete Optimization, IEEE/ACM Trans. Comput. Biology Bioinform.) and conference proceedings (such as ICALP, ESA, IJCAI, FOCS, STOC, STACS, AAAI). He has written 2 books on Parameterized Complexity (with Rod Downey), edited Special Issues, and co-authored book chapters. His publications have received about 15,000 citations, h = 57 (Google Scholar). Papers published in the last five years only have already garnered more than 5300 citations, h=33.

1. Research monograph. R. Downey and M. Fellows. Fundamentals of Parameterized Complexity, Springer, December 2013, 678 citations. A major update of Parameterized Complexity, Springer 1999, 3634 citations.

2. On Problems Without Polynomial Kernels. H. Bodlaender, R. Downey, M. Fellows and D. Hermelin. Journal of Computer and System Sciences 75 (2009) 423–434. Foundation of lower bound methods on kernelization. Some FPT problems do not admit P-sized kernels unless the Polynomial Hierarchy collapses. First presented at ICALP 2009. Mike received the Nerode Prize for this paper. Combined citations: 487.

3. Towards Fully Multivariate Algorithmics: Parameter Ecology and the Deconstruction of Computational Complexity. M. R. Fellows, B. M. P. Jansen and F. A. Rosamond. European J. Combinatorics 34 (2013), 541–566. Ideas herein stimulated the 2013 NII Shonan Conf: Parameterized Complexity and the Understanding, Design, and Analysis of Heuristics. This paper further articulates the Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. M. Fellows, D. Lokshtanov, N. Misra, M. Mnich, F. Rosamnd, S. Saurabh. TCS 45(4), 822-848. Points to new approaches in the design of practical algorithms and the interaction with heuristics. Combined citations: 123.

4. Fixed-Parameter Tractability is Polynomial-Time Extremal Structure Theory I: The Case of Max Leaf. V. Estivill-Castro, M. Fellows, M. Langston and F. Rosamond. Proceedings of ACiD 2005: Algorithms and Complexity in Durham, Kings College London Publications, Texts in Algorithmics 4 (2005), 1–41 and CiE07. Broke new ground in FPT and P-time Extremal Structure with kernelization, bringing the field “full circle” back to the algorithmic consequences of the graph minor structure theory introduced by Robertson and Seymour.Seminal paper establishes FPT extremal structure for the first time. Combined citations: 141.

5. Tight Lower Bounds for Certain Parameterized NP-Hard Problems. J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, I. Kanj and G. Xia. Information and Computation 201 (2005), 216–231. Initially presented at STOC 2005. Launched the prominent XP-optimality program. Combined citations: 119.

6. Cliquewidth is NP-Complete. M. Fellows, F. Rosamond, U. Rotics and S. Szeider. SIAM Journal on Discrete Mathematics 23(2): 909-939 (2009). Proc. ACM Symposium on Theory of Computing (STOC) (2006), 354–362. Solves a problem famously open more than 25 years regarding complexity of “width metrics”. Width metrics beyond treewidth is under intense investigation.Combined citations: 191.

7. On the parameterized complexity of multiple-interval graph problems. M. Fellows, D. Hermelin, F. Rosamond, S. Vialette. Theoretical Computer Science 410 (1)(2009) 53–61. Resolves issues of robustness in the modeling of multi-task scheduling and storage problems. We also develop a useful technique for showing W[1]]-hardness via a reduction from the Multicolored Clique problem, a variant of k-Clique. Citations: 202.

8. Local Search: Is brute-force avoidable? M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh and Y. Villanger. Journal of Computer and System Sciences 78 (2012), 707–719. Pioneering results showing that showed FPT can create the first useful theory of local search. Combined citations: 47.

9. Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments. F. N. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. H. Suters, C. T. Symons. ALENEX/ANALC 62-69 (2004). The new powerful technique of crown reduction is introduced and analyzed. It has been used extensively ever since. Efficient kernelization strategies for vertex cover are developed, implemented and compared experimentally, with applications to computational biology. Citations: 184.

10. Dynamic Dominating Set and Turbo-Charging Greedy Heuristics. R. Downey, J. Egan, M. Fellows, F. Rosamond, and P. Shaw. Tsinghua Science and Technology 19(4) (2014) 329–337. Introduces new perspectives and methodology for bringing parameterizations into heuristics. The paper has already motivated other researchers into this new research direction. Citations: 8.