Publications

bibliometric Information. My research contributions have been internationally recognized. I have 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). I have written 2 books on Parameterized Complexity (with Rod Downey), edited Special Issues, and co-authored book chapters. My publications (total over my career so far) have received more than 14,000 citations, h = 57 (Google Scholar). Papers published in the last ten years only have already garnered more than 5700 citations, h=34.

All Publications By Year

 

2017
  1. Michael R. Fellows: Surfing with Rod. Computability and Complexity 2017: 9-18
  2. Adam R. Day, Michael R. Fellows, Noam Greenberg, Bakhadyr Khoussainov, Alexander G. Melnikov, Frances A. Rosamond: Computability and Complexity – Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. Lecture Notes in Computer Science 10010, Springer 2017, ISBN 978-3-319-50061-4 [contents]

 

2016
  1. Michael R. Fellows: Are you Interested in Theoretical Computer Science? (How Not???) I Have Some Advice for You. Bulletin of the EATCS 119 (2016) [ pdf ]
  2. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, Hadas Shachnai: Tractable Parameterizations for the Minimum Linear Arrangement Problem. TOCT 8(2): 6:1-6:12 (2016) [ pdf ]

 

2015
  1. René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond: Myhill-Nerode Methods for Hypergraphs. Algorithmica 73(4): 696-729 (2015) [ pdf ]
  2. Uéverton dos Santos Souza, Frances A. Rosamond, Michael R. Fellows, Fábio Protti, Maise Dantas da Silva: The Flood-It game parameterized by the vertex cover number. Electronic Notes in Discrete Mathematics 50: 35-40 (2015)
  3. Gábor Erdélyi, Michael R. Fellows, Jörg Rothe, Lena Schend: Control complexity in Bucklin and fallback voting: A theoretical analysis. J. Comput. Syst. Sci. 81(4): 632-660 (2015)
  4. Gábor Erdélyi, Michael R. Fellows, Jörg Rothe, Lena Schend: Control complexity in Bucklin and fallback voting: An experimental analysis. J. Comput. Syst. Sci. 81(4): 661-670 (2015)
  5. Michael R. Fellows, Uéverton dos Santos Souza, Fábio Protti, Maise Dantas da Silva: Tractability and hardness of flood-filling games on trees. Theor. Comput. Sci. 576: 102-116 (2015)
  6. Faisal N. Abu-Khzam, Judith Egan, Michael R. Fellows, Frances A. Rosamond, Peter Shaw: On the parameterized complexity of dynamic problems. Theor. Comput. Sci. 607: 426-434 (2015)

 

2014
  1. Robert Crowston, Michael R. Fellows, Gregory Gutin, Mark Jones, Eun Jung Kim, Fran Rosamond, Imre Z. Ruzsa, Stéphan Thomassé, Anders Yeo: Satisfying more than half of a system of linear equations over GF(2): A multivariate approach. J. Comput. Syst. Sci. 80(4): 687-696 (2014) [ pdf ]
  2. Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, Erik Jan van Leeuwen: Parameterized complexity of firefighting. J. Comput. Syst. Sci. 80(7): 1285-1297 (2014) [ pdf ]
  3. Michael R. Fellows, Bart M. P. Jansen: FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders. TOCT 6(4): 16:1-16:26 (2014)
  4. Faisal N. Abu-Khzam, Judith Egan, Michael R. Fellows, Frances A. Rosamond, Peter Shaw: On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints. COCOA 2014: 625-636

 

2013
  1. Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013, ISBN 978-1-4471-5558-4, pp. I-SSS, 3-707
  2. Michael R. Fellows, Bart M. P. Jansen, Frances A. Rosamond: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3): 541-566 (2013)
  3. Michael R. Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, Frances A. Rosamond: Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable. Theor. Comput. Sci. 472: 81-89 (2013)
  4. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh: Distortion is Fixed Parameter Tractable. TOCT 5(4): 16:1-16:20 (2013)
  5. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, Hadas Shachnai: Tractable Parameterizations for the Minimum Linear Arrangement Problem. ESA 2013: 457-468
  6. René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond: Myhill-Nerode Methods for Hypergraphs. ISAAC 2013: 372-382
  7. Michael R. Fellows, Bart M. P. Jansen: FPT Is Characterized by Useful Obstruction Sets. WG 2013: 261-273
  8. Michael R. Fellows, Xuehou Tan, Binhai Zhu: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Third Joint International Conference, FAW-AAIM 2013, Dalian, China, June 26-28, 2013. Proceedings. Lecture Notes in Computer Science 7924, Springer 2013, ISBN 978-3-642-38755-5 [contents]
  9. Michael R. Fellows, Bart M. P. Jansen: FPT is Characterized by Useful Obstruction Sets. CoRR abs/1305.3102 (2013)

 

2012
  1. Michael Dom, Michael R. Fellows, Frances A. Rosamond, Somnath Sikdar: The Parameterized Complexity of Stabbing Rectangles. Algorithmica 62(1-2): 564-594 (2012)
  2. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond: Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications. Algorithmica 64(1): 3-18 (2012)
  3. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Yngve Villanger: Local search: Is brute-force avoidable? J. Comput. Syst. Sci. 78(3): 707-719 (2012)
  4. Michael R. Fellows, Serge Gaspers, Frances A. Rosamond: Parameterizing by the Number of Numbers. Theory Comput. Syst. 50(4): 675-693 (2012)
  5. Michael R. Fellows, Andreas Pfandler, Frances A. Rosamond, Stefan Rümmele: The Parameterized Complexity of Abduction. AAAI 2012
  6. Leo Brueggeman, Michael R. Fellows, Rudolf Fleischer, Martin Lackner, Christian Komusiewicz, Yiannis Koutis, Andreas Pfandler, Frances A. Rosamond: Train Marshalling Is Fixed Parameter Tractable. FUN 2012: 51-56
  7. Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, Hadas Shachnai: Parameterized Approximation via Fidelity Preserving Transformations. ICALP (1) 2012: 351-362
  8. René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond: How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding. CoRR abs/1211.1299 (2012)
  9. Michael R. Fellows, Jiong Guo, Dániel Marx, Saket Saurabh: Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). Dagstuhl Reports 2(6): 26-50 (2012)

 

2011
  1. Hans L. Bodlaender, Michael R. Fellows, Michael A. Langston, Mark A. Ragan, Frances A. Rosamond, Mark Weyer: Quadratic Kernelization for Convex Recoloring of Trees. Algorithmica 61(2): 362-388 (2011)
  2. Michael R. Fellows, Henning Fernau: Facility location problems: A parameterized view. Discrete Applied Mathematics 159(11): 1118-1130 (2011)
  3. Michael R. Fellows, Fedor V. Fomin, Gregory Gutin: Special Issue on Parameterized Complexity of Discrete Optimization. Discrete Optimization 8(1): 1 (2011)
  4. Michael R. Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann: Graph-based data clustering with overlaps. Discrete Optimization 8(1): 2-17 (2011)
  5. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2): 143-153 (2011)
  6. Michael R. Fellows, Guillaume Fertin, Danny Hermelin, Stéphane Vialette: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4): 799-811 (2011)
  7. Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier: A generalization of Nemhauser and Trotterʼs local optimization theorem. J. Comput. Syst. Sci. 77(6): 1141-1158 (2011)
  8. Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier: Parameterized Algorithmics for Finding Connected Motifs in Biological Networks. IEEE/ACM Trans. Comput. Biology Bioinform. 8(5): 1296-1308 (2011)
  9. Michael R. Fellows, Tzvika Hartman, Danny Hermelin, Gad M. Landau, Frances A. Rosamond, Liat Rozenberg: Haplotype Inference Constrained by Plausible Haplotype Data. IEEE/ACM Trans. Comput. Biology Bioinform. 8(6): 1692-1699 (2011)
  10. Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. TOCT 2(2): 5:1-5:23 (2011)
  11. Michael R. Fellows: Recent Developments in the Theory of Pre-processing. FAW-AAIM 2011: 4-5
  12. Robert Crowston, Michael R. Fellows, Gregory Gutin, Mark Jones, Frances A. Rosamond, Stéphan Thomassé, Anders Yeo: Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average. FSTTCS 2011: 229-240
  13. Michael R. Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, Frances A. Rosamond: Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable. IJCAI 2011: 522-527
  14. Cristina Bazgan, Morgan Chopin, Michael R. Fellows: Parameterized Complexity of the Firefighter Problem. ISAAC 2011: 643-652
  15. Michael R. Fellows, Serge Gaspers, Frances A. Rosamond: Multivariate Complexity Theory. Computer Science, The Hardware, Software and Heart of It 2011: 269-293
  16. Gábor Erdélyi, Michael R. Fellows, Lena Piras, Jörg Rothe: Control Complexity in Bucklin and Fallback Voting. CoRR abs/1103.2230 (2011)

 

2010
  1. Fellows, M. R., Fomin, F. V., and Gutin, G. Special Issue on Parameterized Complexity. Discrete Optimization (2010). To Appear. [ bib ]
  2. Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. Computer and System Sciences (2010). To Appear. [ bib ]
  3. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. Journal of Computer and System Sciences (2010). To Appear. [ bib ]

 

2009
  1. Fellows, M. R., Hermelin, D., and Rosamond, F. A. Well-quasi-ordering bounded treewidth graphs. In Proceedings of International Workshop on Parameterized and Exact Computation, IWPEC’09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | pdf ]
  2. Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | pdf ]
  3. Fellows, M. R., Hermelin, D., Rosamond, F. A., and Vialette, S. On the parameterized complexity of multiple-interval graph problems. Journal of Theoretical Computer Science 410, 1 (2009), 53-61. [ bib | pdf ]
  4. Fellows, M. R., Guo, J., Komusiewicz, C., Niedermeier, R., and Uhlmann, J. Graph-based data clustering with overlaps. In Proceedings of COCOON (2009), vol. 5609 of Lecture Notes in Computer Science, Springer, pp. 516-526. [ bib | pdf ]
  5. Fellows, M. R., Guo, J., and Kanj, I. The parameterized complexity of some minimum label problems. In Proceedings of WG (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | pdf ]
  6. Fellows, M. R., Hartman, T., Hermelin, D., Landau, G. M., Rosamond, F. A., and Rozenberg, L. Haplotype inference constrained by plausible haplotype data. In Proceedings of the of the 20th Combinatorial Pattern Matching conference, CPM (2009), pp. 339-352. [ bib | pdf ]
  7. Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. Fixed-parameter algorithms for Kemeny Rankings. Theoretical Computer Science (2009). Accepted for publication, August 2009, 30 pages. [ bib | pdf ]
  8. Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. How similarity helps to efficiently compute Kemeny Rankings. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS (2009), pp. 657-664. [ bib | pdf ]
  9. Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixed-parameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE’09(2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | pdf ]
  10. Fellows, M. R., Guo, J., Moser, H., and Niedermeier, R. A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In Proceedings of MFCS’09 (2009), vol. 5734 of Lecture Notes in Computer Science, Springer-Verlag, pp. 319-330. [ bib | pdf ]
  11. Enciso, R., Fellows, M. R., Guo, J., Kanj, I., Rosamond, F., and Suchy, A. What makes equitable connected partition easy? In Proceedings of International Workshop of Parameterized and Exact Computation, IWPEC’09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib ]
  12. Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., and Villanger, Y. Local search: Is brute force avoidable? In Proceedings International Joint Conference on Artificial Intelligence, IJCAI’09 (2009). To Appear. [ bib | pdf ]
  13. Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP’09 (Track A) (2009), pp. 463-474. [ bib | pdf ]
  14. Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Parameterized low-distortion embeddings – graph metrics into lines and trees. Tech. rep., 2009. Manuscript. [ bib ]
  15. Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F., Whitesides, S., and Yu, N. On the parameterized complexity of the discrete milling problem with turn costs. InProceedings of FST TCS’09 (2009), Springer-Verlag. To Appear. [ bib ]
  16. M. Dom, M. F., and Rosamond, F. Parameterized complexity of stabbing rectangles and squares in the plane. In Proceedings of the 3rd Workshop on Algorithms and Computation, WALCOM’09 (2009), vol. 5431 of Lecture Notes in Computer Science, Springer-Verlag, pp. 298-309. [ bib | pdf ]
  17. Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822-848. [ bib | pdf ]
  18. Fellows, M., Guo, J., Moser, H., and Niedermeier, R. A generalization of Nemhauser and Trotter’s local optimization algorithm. In Proceedings of STACS’09 (2009), pp. 409-420. [ bib | pdf ]
  19. Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixed-parameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE’09(2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | pdf ]
  20. Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA’09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | pdf ]
  21. Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822-848. [ bib | pdf ]
  22. Bodlaender, H., Fellows, M., Langston, M., Ragan, M., Rosamond, F., and Weyer, M. Quadratic kernelization for convex recoloring of trees. Algorithmica (2009). Accepted to Algorithmica. [ bib | pdf ]
  23. Bodlaender, H., Fellows, M., and Thilikos, D. Derivation of algorithms for cutwidth and related graph layout parameters. Journal of Computer and System Sciences 75 (2009). [ bib ]
  24. Fellows, M., Rosamond, F., Rotics, U., and Szeider, S. Cliquewidth is NP-Complete. SIAM Journal on Discrete Mathematics (SIDMA) 23, 2 (2009). A preliminary and shortened version of this paper appeared in the proceedings of STOC 2006; 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA, pp. 354—362, ACM Press, 2006. This paper combines the results of the technical reports: Proving NP-Hardness for Clique-Width I: Non-approximability of Sequential Clique-width, and, Proving NP-Hardness for Clique-Width II: Non-approximability of Clique-width; Electronic Colloquium on Computational Complexity (ECCC). [ bib | pdf | pdf ]
  25. Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP 2009 (Track A)(2009), pp. 463-474. [ bib | pdf ]
  26. Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Parameterized low-distortion embeddings – graph metrics into lines and trees. Tech. rep., 2009. Manuscript. [ bib ]

 

2008
  1. Downey, R., Fellows, M., and Langston, M. The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors. The Computer Journal 51, 1 (2008), 1-6. The Computer Journal published a two-issue special on Parameterized Complexity that includes 15 survey articles, as well as an Introduction and Overview. The issues are Volume 51, 2008, Issue 1 and Issue 3. [ bib | pdf ]
  2. Bodlaender, H. L., Demaine, E. D., Fellows, M. R., Guo, J., Hermelin, D., Lokshtanov, D., Müller, M., Venkatesh Raman, J. v. R., and Rosamond, F. A. Open problems in parameterized and exact computation from iwpec 2008. Tech. Rep. UU-CS-2008-017, Department of Information and Computing Sciences, Utrecht University, 2008. [ bib | pdf ]
  3. Betzler, N., Fellows, M. R., Komusiewicz, C., and Niedermeier, R. Parameterized algorithms and hardness results for some graph motif problems. In Proceedings of Combinatorial Pattern Matching, 19th Annual Symposium, CPM, (2008), P. Ferragina and G. M. Landau, Eds., vol. 5029 of Lecture Notes in Computer Science, Springer, pp. 31-43. [ bib | pdf ]
  4. Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Fixed-parameter algorithms for Kemeny scores. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, Springer-Verlag, pp. 60-71. [ bib | pdf ]
  5. Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Computing Kemeny Rankings, parameterized by the average K-T distance. In Proceedings of the 2nd International Workshop on Computational Social Choice, COMSOC (2008). [ bib | pdf ]
  6. Fellows, M. R., Rosamond, F., and Spdfo, A. Sensing God’s Will is fixed parameter tractable. Tech. rep., University of Auckland, New Zealand, 2008. University of Auckland, NZ Mathematics Research Report, 9 pages. [ bib | pdf ]
  7. Fellows, M. R., Hermelin, D., Müller, M., and Rosamond, F. A. A purely democratic characterization of W[1]. In Proceedings of Parameterized and Exact Computation, Third International Workshop IWPEC’08 (2008), M. Grohe and R. Niedermeier, Eds., vol. 5018 of Lecture Notes in Computer Science, Springer-Verlag, pp. 103-114. [ bib | pdf ]
  8. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP’08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer, pp. 563-574. [ bib | pdf ]
  9. Fellows, M., Flum, J., Hermelin, D., Muller, M., and Rosamond, F. W-hierarchies defined by symmetric gates. Theory of Computing Systems (2008). [ bib | pdf ]
  10. Fellows, M., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of AAIM’08 (2008), vol. 5034 of Lecture Notes in Computer Science, Springer, pp. 188-199. [ bib | pdf ]
  11. Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D., and Whitesides, S. Faster fixed parameter tractable algorithms for matching and packing problems. Algorithmica 52, 2 (2008), 167-176. [ bib | pdf ]
  12. Dujmovic, V., Fellows, M. R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. Algorithmica 52, 2 (2008), 267-292. [ bib | pdf ]
  13. Fellows, M. R., Meister, D., Rosamond, F. A., Sritharan, R., and Telle, J. A. Leaf powers and their properties: Using the trees. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.-H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, Springer-Verlag, pp. 402-413. [ bib | pdf ]
  14. Fellows, M. R., Lokshtanov, D., Misra, N., Rosamond, F. A., and Saurabh, S. Graph layout problems parameterized by vertex cover. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.-H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, Springer-Verlag, pp. 294-305. [ bib | pdf ]
  15. Bodlaender, H. L., Fellows, M. R., Heggernes, P., Mancini, F., Papadopoulos, C., and Rosamond, F. A. Clustering with partial information. In Proceedings of Mathematical Foundations of Computer Science, 33rd International Symposium, MFCS 2008, Torun, Poland (2008), E. Ochmanski and J. Tyszkiewicz, Eds., vol. 5162 of Lecture Notes in Computer Science, Springer-Verlag, pp. 144-155. [ bib | pdf ]
  16. Fellows, M. R., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM’08 (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, Springer-Verlag, pp. 188-199. [ bib | pdf ]
  17. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP’08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer-Verlag, pp. 563-574. [ bib | pdf ]

 

2007
  1. Fellows, M. R., and Rosamond, F. A. The complexity ecology of parameters: An illustration using bounded max leaf number. In Proceedings of Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE, Siena, Italy (2007), S. B. Cooper, B. Löwe, and A. Sorbi, Eds., vol. 4497 of Lecture Notes in Computer Science, Springer, pp. 268-277. [ bib | pdf ]
  2. Fellows, M., and Rosamond, F. Why is P Not Equal to NP? In Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007: Local Proceedings (2007). [ bib | pdf ]
  3. Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In Proceedings of Automata, Languages and Programming, 34th International Colloquium, ICALP (2007), L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, Eds., vol. 4596 of Lecture Notes in Computer Science, Springer, pp. 340-351. [ bib | pdf ]
  4. Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Fundamentals of Computation Theory, 16th International Symposium, FCT, Budapest, Hungary (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer, pp. 312-321. [ bib | pdf ]
  5. Christian, R., Fellows, M. R., Rosamond, F., and Spdfo, A. On the complexity of lobbying in multiple referenda. Review of Economic Design 11 (2007), 217-224. [ bib | pdf ]
  6. Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., and Thomassen., C. On the complexity of some colorful problems parameterized by treewidth. (invited paper). In Proceedings of First International Conference on Combinatorial Optimization and Applications COCOA’07 (2007), vol. 4616 of Lecture Notes in Computer Science, Springer-Verlag, pp. 366-377. [ bib | pdf ]
  7. Cai, L., Fellows, M., Juedes, D., and Rosamond, F. The complexity of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. [ bib | pdf ]
  8. Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. [ bib | pdf ]
  9. Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. [ bib | pdf ]
  10. Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON’07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 86-96. [ bib | pdf ]
  11. Fellows, M. R., Fomin, F. V., Lokshtanov, D., Rosamond, F. A., Saurabh, S., Szeider, S., and Thomassen, C. On the complexity of some colorful problems parameterized by treewidth. InProceedings of Combinatorial Optimization and Applications, COCOA’07 (2007), A. W. M. Dress, Y. Xu, and B. Zhu, Eds., vol. 4616 of Lecture Notes in Computer Science, Springer-Verlag, pp. 366-377. [ bib | pdf ]
  12. Chor, B., Fellows, M. R., Ragan, M. A., Razgon, I., Rosamond, F. A., and Snir, S. Connected coloring completion for general graphs: Algorithms and complexity. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON’07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 75-85. [ bib | pdf ]
  13. Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of 16th International Symposium Fundamentals of Computation Theory FCT’07 (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. [ bib |pdf ]
  14. Cai, L., Fellows, M., Juedes, D., and Rosamond, F. The complexity of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. [ bib | pdf ]
  15. Abu-Khzam, F. N., Fellows, M. R., Langston, M. A., and Suters, W. H. Crown structures for vertex cover kernelization. Theory of Computing Systems 41, 3 (2007), 411-430. [ bib |pdf ]
  16. Dehne, F., Fellows, M., Langston, M., Rosamond, F., and Stevens, K. An o(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. Theory of Computing Systems 41, 3 (2007), 479-492. [ bib | pdf ]
  17. Abu-Khzam, F. N., Fellows, M. R., Langston, M. A., and Suters, W. H. Crown structures for vertex cover kernelization. Theory of Computing Systems 41, 3 (2007), 411-431. [ bib |pdf ]
  18. Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of Fundamentals of Computation Theory, 16th International Symposium, FCT’07 (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. [ bib | pdf ]
  19. Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of Fundamentals of Computation Theory, 16th International Symposium, FCT’07 (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. [ bib | pdf ]
  20. Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON’07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 86-96. [ bib | pdf ]
  21. Cai, L., Fellows, M., Juedes, D., and Rosamond, F. On the efficiency of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. [ bib | pdf ]
  22. Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. [ bib | pdf ]

 

2006
  1. Fellows, M. The lost continent of polynomial time. In Proceedings of IWPEC’06 (2006), vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, p. 276 – 277. [ bib | pdf ]
  2. Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167. [ bib | pdf ]
  3. Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixed-parameter approach to 2-layer planarization. Algorithmica 45, 2 (2006), 159-182. [ bib | pdf ]
  4. Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167. [ bib | pdf ]
  5. Dehne, F., Fellows, M. R., Fernau, H., Prieto, E., and Rosamond, F. A. NONBLOCKER: Parameterized algorithmics for minimum dominating set. In Proceedings of Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM’06 (2006), J. Wiedermann, G. Tel, J. Pokorný, M. Bieliková, and J. Stuller, Eds., vol. 3831 of Lecture Notes in Computer Science, Springer-Verlag, pp. 237-245. [ bib | pdf ]
  6. Fellows, M. R., Rosamond, F. A., Rotics, U., and Szeider, S. Clique-width minimization is NP-hard. In Proceedings of the 38th Annual Symposium on Theory of Computing, ACM’06(2006), J. M. Kleinberg, Ed., ACM, pp. 354-362. [ bib | pdf ]
  7. Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC’06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, pp. 192-202. [ bib | pdf ]
  8. Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Kernelization for convex recoloring. In Proceedings of Algorithms and Complexity in Durham, ACiD’06 (2006), H. Broersma, S. S. Dantchev, M. J. 0002, and S. Szeider, Eds., vol. 7 of Texts in Algorithmics, King’s College, London, pp. 23-36. Accepted to Algorithmica. [ bib | pdf ]
  9. Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC’06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, pp. 192-202. [ bib | pdf ]
  10. Fellows, M. The lost continent of polynomial time. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC’06 (2006), vol. 4169 ofLecture Notes in Computer Science, Springer-Verlag, p. 276 – 277. [ bib | pdf ]
  11. Downey, R. G., Fellows, M. R., and McCartin, C. Parameterized approximation problems. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC’06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer, pp. 121-129. [ bib ]
  12. Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. Theoretical Computer Science 351 (2006), 351-359. [ bib | pdf ]

 

2005
  1. Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D. W., Kanj, I. A., and Xia, G. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201, 2 (2005), 216-231. [ bib | pdf ]
  2. Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F., and Stege, U. A refined search tree technique for dominating set on planar graphs. Journal of Computer and System Sciences 71, 4 (2005), 385-405. [ bib | pdf ]
  3. Dehne, F. K. H. A., Fellows, M. R., Langston, M. A., Rosamond, F. A., and Stevens, K. An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of Computing and Combinatorics, 11th Annual International Conference, COCOON’05 (2005), L. Wang, Ed., vol. 3595 of Lecture Notes in Computer Science, Springer-Verlag, pp. 859-869. [ bib | pdf ]
  4. Estivill-Castro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixed-parameter tractability is polynomial-time extremal structure theory I: The case of max leaf. In Proceedings of Algorithms and Complexity in Durham, ACiD 2005 (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King’s College, London, pp. 1-41. [ bib | pdf ]
  5. Estivill-Castro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixed-parameter tractability is polynomial-time extremal structure theory I: The case of max leaf. In Algorithms and Complexity in Durham 2005 – Proceedings of the First ACiD (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King’s College, London, pp. 1-41. [ bib | pdf ]

 

2004
  1. Dehne, F. K., Fellows, M. R., Rosamond, F. A., and Shaw, P. Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In Proceedings of Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway(2004), R. G. Downey, M. R. Fellows, and F. K. Dehne, Eds., vol. 3162 of Lecture Notes in Computer Science, Springer, pp. 271-280. [ bib | pdf ]
  2. Fellows, M. R. A survey of FPT algorithm design techniques with an emphasis on recent advances and connections to practical computing. In Proceedings of 12th Annual European Symposium ESA, Bergen, Norway (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-2. [ bib | pdf ]
  3. Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384. [ bib | pdf ]
  4. Ellis, J., Fan, H., and Fellows, M. The dominating set problem is fixed parameter tractable for graphs of bounded genus. Journal of Algorithms 52, 2 (2004), 152-168. [ bib ]
  5. Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the Vertex Cover problem: Theory and experiments. InProceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX’04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 62-69. [ bib ]
  6. Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F. A., Stege, U., Thilikos, D. M., and Whitesides, S. Faster fixed-parameter tractable algorithms for matching and packing problems. In Proceedings of 12th Annual European Symposium on Algorithms ESA’04 (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, Springer-Verlag, pp. 311-322. [ bib | pdf ]
  7. Fellows, M., Heggernes, P., Rosamond, F. A., Sloper, C., and Telle, J. A. Finding k disjoint triangles in an arbitrary graph. In Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG’04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 235-244. [ bib | pdf ]
  8. Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG’04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 257-269. [ bib | pdf ]
  9. Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384. [ bib | pdf ]
  10. Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the vertex cover problem: Theory and experiments. InProceedings of the sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX’04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 62-69. [ bib ]
  11. Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Graph-Theoretic Concepts in Computer Science, 30th International Workshop WG’04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 257-269. [ bib | pdf ]
  12. Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. In Proceedings of the First International Workshop on Parameterized and Exact Computation IWPEC’04 (2004), vol. 3162 of Lecture Notes in Computer Science, Springer-Verlag, pp. 223-234. [ bib | pdf ]

 

2003
  1. Chen, J., and Fellows, M. Foreword from the Guest Editors. Journal of Computer and System Sciences 67 (2003), 653-654. Special Issue on Parameterized Complexity,. [ bib ]
  2. Fellows, M. R. Blow-ups, win/win’s, and crown rules: Some new directions in FPT. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’2003, Elspeet, The Netherlands (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-12. [ bib | pdf ]
  3. Fellows, M. R. New directions and new challenges in algorithm design and complexity, parameterized. In Proceedings of Algorithms and Data Structures, 8th International Workshop WADS (2003), F. K. H. A. Dehne, J.-R. Sack, and M. H. M. Smid, Eds., vol. 2748 of Lecture Notes in Computer Science, Springer-Verlag, pp. 505-520. [ bib | pdf ]
  4. Fellows, M. R., Hallett, M., and Stege, U. Analogs & duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 – 216. [ bib | pdf ]
  5. Fellows, M. R., Hallett, M., and Stege, U. Analogs & duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 – 216. [ bib | pdf ]
  6. Bell, T., Fellows, M., Witten, I., and Koblitz, N. Explaining cryptographic systems to the general public. Computers and Education 40 (2003), 199-215. [ bib ]
  7. Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic ideas to the general public. Computers and Education 40 (2003), 199—215. [ bib | pdf ]
  8. Fellows, M. R., Hallett, M., and Stege, U. Analogs and duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 – 216. [ bib | pdf ]
  9. Downey, R. G., Estivill-Castro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205-218. [ bib | pdf ]
  10. Downey, R. G., Estivill-Castro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205-218. [ bib | pdf ]
  11. Fellows, M. R. Blow-ups, win/win’s, and crown rules: Some new directions in FPT. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’03 (2003), H. L. Bodlaender, Ed., vol. 2880 of LNCS, Springer-Verlag, pp. 1-12. [ bib | pdf ]
  12. Dehne, F., Fellows, M. R., and Rosamond, F. A. An FPT algorithm for set splitting. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’03 (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science, Springer-Verlag, pp. 180-191. [ bib | pdf ]
  13. Bodlaender, H. L., Fellows, M. R., and Thilikos, D. M. Starting with nondeterminism: The systematic derivation of linear-time graph layout algorithms. In Proceedings of Mathematical Foundations of Computer Science MFCS’03 (2003), B. Rovan and P. Vojtás, Eds., vol. 2747 of Lecture Notes in Computer Science, Springer, pp. 239-248. [ bib | pdf ]
  14. Fellows, M., and McCartin, C. On the parameterized complexity of minimizing tardy tasks. Theoretical Computer Science A 298 (2003), 317-324. [ bib ]

 

2002
  1. Fellows, M. R. Parameterized complexity: The main ideas and connections to practical computing. In Experimental Algorithmics (2002), R. Fleischer, B. M. E. Moret, and E. M. Schmidt, Eds., vol. 2547 of Lecture Notes in Computer Science, Springer-Verlag, pp. 51-77. [ bib | pdf ]
  2. Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of closest substring and related problems. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS’02 (2002), H. Alt and A. Ferreira, Eds., vol. 2285 of Lecture Notes in Computer Science, Springer-Verlag, pp. 262-273. [ bib |pdf ]
  3. Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of 8th Scandinavian Workshop on Algorithm Theory SWAT’02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer, pp. 150-159. [ bib | pdf ]
  4. Ellis, J., Fan, H., and Fellows, M. R. The dominating set problem is fixed parameter tractable for graphs of bounded genus. In Proceedings of SWAT 2002: Scandinavian Workshop on Algorithm Theory (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of LNCS, Springer, pp. 180-189. [ bib | pdf ]
  5. Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory SWAT’02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer-Verlag, pp. 150-159. [ bib | pdf ]
  6. Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of closest substring and related problems. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS’02 (2002), H. Alt and A. Ferreira, Eds., vol. 2285 of LNCS, Springer-Verlag, pp. 262-273. [ bib | pdf ]

 

2001
  1. Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Discrete Mathematics 230, 1-3 (2001), 215-252. [ bib | pdf ]
  2. Fellows, M. R. Parameterized complexity: New developments and research frontiers. In Aspects of Complexity (2001), De Gruyter, pp. 51-72. [ bib | pdf ]
  3. Fellows, M. R. Some new developments in parameterized complexity. In Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms (2001), E. T. Baskoro, Ed., pp. 43-44. [ bib | pdf ]
  4. Fellows, M. R. Parameterized complexity: Main ideas, connections to heuristics and research frontiers. In Proceedings of ISAAC (2001), vol. 2223 of Lecture Notes in Computer Science, Springer-Verlag, pp. 291-307. [ bib | pdf ]
  5. Downey, R. G., and Fellows, M. R. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348. [ bib | pdf ]
  6. Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixed-parameter approach to two-layer planarization. In Proceedings of the 9th International Symposium on Graph Drawing GD’01 (2001), vol. 2265 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-15. [ bib | pdf ]
  7. Dujmović, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Suderman, M., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA ’01 (2001), vol. 2161 of Lecture Notes in Computer Science, Springer-Verlag, pp. 488-499. [ bib ]
  8. Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F. A., and Stege, U. A refined search tree technique for DOMINATING SET on planar graphs. InProceedings of 26th International Symposium Mathematical Foundations of Computer Science, MFCS’01 (2001), J. Sgall, A. Pultr, and P. Kolman, Eds., vol. 2136 of Lecture Notes in Computer Science, Springer-Verlag, pp. 111-122. [ bib | pdf ]
  9. Downey, R., and Fellows, M. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348. [ bib | pdf ]

 

2000
  1. Cattell, K., Dinneen, M. J., Downey, R. G., and Fellows, M. R. On computing graph minor obstruction sets. Theoretical Computer Science 233, 1 (2000), 107-127. [ bib | pdf ]
  2. Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and Warnow, T. J. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science A 244, 1-2 (2000), 167-188. [ bib | pdf ]
  3. Downey, R. G., Fellows, M. R., and Raman, V. The complexity of irredundant sets parameterized by size. Discrete Applied Mathematics 100, 3 (2000), 155-167. [ bib | pdf ]
  4. Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and Warnow, T. J. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science A 244, 1-2 (2000), 167-188. [ bib | pdf ]
  5. Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings of Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS ’00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 ofLecture Notes in Computer Science, Springer-Verlag, pp. 240-251. [ bib | pdf ]
  6. Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS’00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 ofLecture Notes in Computer Science, Springer-Verlag, pp. 240-251. [ bib | pdf ]

 

1999
  1. Downey, R. G., and Fellows, M. R. Parameterized Complexity. Springer-Verlag, 1999. 530 pp. [ bib ]
  2. Downey, R. G., Fellows, M. R., and Stege, U. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, vol. 49 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. DIMACS, 1999, pp. 49-99. [ bib | pdf ]
  3. Downey, R. G., Fellows, M. R., and Stege, U. Computational Tractability: A View from Mars. Tech. rep., 1999. [ bib | pdf ]
  4. Downey, R. G., and Fellows, M. R. Parameterized complexity after (almost) 10 years: Review and open questions. In Proceedings of Combinatorics, Computation and Logic, DMTCS’99 and CATS’99 (Singapore, 1999), vol. 21 of Australian Computer Science Communications, Springer-Verlag, pp. 1-33. [ bib | pdf ]
  5. Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems in coding theory. SIAM Journal of Computing 29, 2 (1999), 545-570. [ bib | pdf ]
  6. Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic systems to the general public. In Proceedings of the First IFIP World Conference on Information Security Education (WISE) (1999), L. Yngstgröm and S. Fischer-Hübner, Eds., vol. 99-008, Stockholm University Report Series, p. 221—233. [ bib ]

 

1998
  1. Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U. Analogs and duals of the MAST problem for sequences and trees. In Proceedings of the 6th Annual European Symposium on Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P. cci, Eds., no. 1461 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 103-114. [ bib | pdf ]
  2. Fellows, M., Hallett, M., and Stege, U. On the multiple gene duplication problem. In Proceedings of the 9th International Symposium on Algorithms and Computation, ISAAC’98(1998), K.-Y. Chwa and O. H. Ibarra, Eds., vol. 1533 of Lecture Notes in Computer Science, Springer-Verlag, pp. 347-356. [ bib | pdf ]
  3. Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 1-2 (1998), 123-140. [ bib | pdf ]
  4. Downey, R. G., Fellows, M. R., and Regan, K. W. Parameterized circuit complexity and the W hierarchy. Theoretical Computer Science A 191, 1-2 (1998), 97-115. [ bib | pdf ]
  5. Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U. Analogs and duals of the MAST problem for sequences and trees. In Proceedings of the 6th Annual European Symposium on Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P. cci, Eds., no. 1461 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 103-114. [ bib | pdf ]
  6. Balasubramanian, Fellows, and Raman. An improved fixed-parameter algorithm for vertex cover. IPL: Information Processing Letters 65, 3 (1998), 163-168. [ bib | pdf ]
  7. Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 1-2 (1998), 123-140. [ bib | pdf ]
  8. Fellows, M., Hell, P., and Seyffarth, K. Constructions of dense planar networks. Networks 32 (1998), 275-281. [ bib ]

 

1997
  1. Courcelle, B., Downey, R. G., and Fellows, M. R. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science 3, 11 (1997), 1194-1198. [ bib | pdf ]
  2. Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84, 1 (1997), 119-138. [ bib | pdf ]
  3. Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. The parameterized complexity of short computation and factorization. Archive for Mathematical Logic 36 (1997), 321-338. [ bib |pdf ]
  4. Downey, R., Fellows, M., and Regan, K. Descriptive complexity and the W hierarchy. In Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, Eds., AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997, pp. 119-134. [ bib | pdf ]
  5. Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems of linear codes and integral lattices. Tech. rep., 1997. Manuscript. [ bib | pdf ]
  6. Casey, N., and Fellows, M. Implementing the standards: Let’s focus on the first four. DIMACS Series: Discrete Mathematics in the Schools. How Can We Have an Impact? (1997). [ bib | pdf ]

 

1996
  1. Bell, T., Fellows, M. R., and Witten, I. Computer Science Unplugged … offline activities and games for all ages: Teacher Edition. Computer Science Unplugged, 1996. There are currently two versions of the book. The “Teachers’ Edition” which is aimed at people with less of a technical background. It has 12 activities, and a lot more illustrations and handouts. Both books are available in Download from http://www.lulu.com. [ bib ]
  2. Fellows, M. R., Bell, T., and Witten, I. Computer Science Unplugged … offline activities and games for all ages: Original Activities Book. Computer Science Unplugged, 1996. [ bib ]
  3. Cattell, K., Dinneen, M. J., and Fellows, M. R. A simple linear-time algorithm for finding path-decompositions of small width. Information Processing Letters 57, 4 (1996), 197-203. [ bib | pdf ]
  4. Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Tech. rep., 1996. Preprint. Journal publication is “Discrete Mathematics” (2000),. [ bib | pdf ]
  5. Bailey, I., Cattell, K., Fellows, M. R., Koop, B., Olafson, R., Olafson, R., and Upton, C. Approaches to detection of distantly related proteins by database searches. BioTechniques 21(1996), 1118 – 1125. [ bib ]
  6. Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Combinatorics, Complexity, and Logic – Proceedings of DMTCS ’96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., Springer-Verlag, pp. 194-213. [ bib | pdf ]
  7. Cesati, M., and Fellows, M. Sparse parameterized problems. Annals of Pure and Applied Logic 82 (1996), 1-15. [ bib | pdf ]
  8. Fellows, M. The heart of puzzling: Mathematics and computer games. In Proceedings of the 1996 Computer Games Developers Conference (1996), Miller Freeman, p. 109—120. [ bib | pdf ]
  9. Alon, N., Fellows, M. R., and Hare, D. R. Vertex transversals that dominate. Journal of Graph Theory 21, 1 (1996), 21-32. [ bib | pdf ]
  10. Cattell, K., Dinneen, M. J., and Fellows, M. R. A simple linear-time algorithm for finding path-decompositions of small width. Information Processing Letters 57, 4 (1996), 197-203. [ bib | pdf ]
  11. Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Proceedings of Combinatorics, Complexity, and Logic, DMTCS’96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., Springer-Verlag, pp. 194-213. [ bib | pdf ]
  12. Alon, N., Fellows, M., and Hare, D. O. Vertex transversals that dominate. Journal of Graph Theory 21 (1996), 21-32. [ bib | pdf ]
  13. Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finite-state computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM 2006 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384-391. [ bib ]
  14. Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finite-state computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM’96 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384-391. [ bib ]

 

1995
  1. Fellows, M., Kratochvil, J., Middendorf, M., and Pfeiffer, F. The complexity of induced minors and related problems. Algorithmica 13, 3 (1995), 266-282. [ bib | pdf ]
  2. Cattell, K., Dinneen, M. J., and Fellows, M. R. Obstructions to within a few vertices or edges of acyclic. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS’95 (1995), S. G. Akl, F. Dehne, J.-R. Sack, and N. Santoro, Eds., vol. 955 of Lecture Notes in Computer Science, Springer-Verlag, pp. 415-427. [ bib | pdf ]
  3. Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235-276. [ bib | pdf ]
  4. Cai, L., Chen, J., Downey, R., and Fellows, M. On the structure of parameterized problems in NP. Information and Computation 123, 1 (1995), 38-49. [ bib ]
  5. Downey, R. G., and Fellows, M. R. Parameterized computational feasibility. In Proceedings of the Second Cornell Workshop on Feasible Mathematics. Feasible Mathematics II(Boston, 1995), P. Clote and J. Remmel, Eds., Birkhäuser, pp. 219-244. [ bib | pdf ]
  6. Downey, R., and Fellows, M. R. Fixed-parameter tractability and completeness II: Completeness for W[1]. Theoretical Computer Science A 141 (1995), 109-131. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. [ bib | pdf ]
  7. Downey, R., and Fellows, M. R. Fixed-parameter tractability and completeness I: Basic theory. Siam Journal of Computing 24 (1995), 873-921. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. [ bib | pdf ]
  8. Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 49-57. [ bib | pdf ]
  9. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 31-54. [ bib | pdf ]
  10. Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235-276. [ bib | pdf ]
  11. Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141, 1&2 (1995), 109-131. [ bib | pdf ]
  12. Cai, L., Chen, J., Downey, R., and Fellows, M. On the structure of parameterized problems in NP. Information and Computation 123, 1 (1995), 38-49. [ bib ]
  13. Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal of Computing 24, 4 (1995), 873-921. [ bib | pdf ]
  14. Bodlaender, H., and Fellows, M. On the complexity of k-processor scheduling. Operations Research Letters 18 (1995), 93 – 98. [ bib | pdf ]
  15. Fellows, M., Hell, P., and Seyffarth, K. Large planar graphs with given diameter and maximum degree. Discrete Applied Math 61 (1995), 133-153. [ bib ]
  16. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 31-54. [ bib | pdf ]
  17. Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 49-57. [ bib | pdf ]

 

1994
  1. Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomial-time algorithms. Journal of Computer and System Sciences (1994), 769-779. [ bib | pdf ]
  2. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Proceedings of Combinatorial Pattern Matching, 5th Annual Symposium, CPM (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 15-30. [ bib ]
  3. Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Proceedings of the IEEE Computer Society Workshop on Shape and Pattern Recognition in Computational Biology (1994), 99-116. IBM TJ Watson Research Center Publication. [ bib ]
  4. Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. On the structure of parameterized problems in NP. In Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science, STACS’94, Caen, France (1994), P. Enjalbert, E. W. Mayr, and K. W. Wagner, Eds., vol. 775 of Lecture Notes in Computer Science, Springer, pp. 509-520. [ bib ]
  5. Fellows, M., and Koblitz, N. Combinatorial cryptosystems galore! In Proceedings of the Second International Symposium on Finite Fields, Las Vegas, Nevada, August, 1993 (1994), vol. 168 of Contemporary Mathematics, American Mathematical Society, pp. 51-61. [ bib | pdf ]
  6. Fellows, M., Hibner, A., and Koblitz, N. Cultural aspects of mathematics education reform. Notices of the American Mathematics Society 41 (1994), 5—9. [ bib ]
  7. Fellows, M., Fricke, G., Hedetniemi, S., and Jacobs, D. The private neighbor cube. SIAM Journal on Discrete Mathematics 7, 1 (1994), 41-47. [ bib ]
  8. Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC’94 (New York, 1994), ACM Press, pp. 449-458. [ bib | pdf ]
  9. Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC’94 (1994), ACM Press, pp. 449-458. [ bib | pdf ]
  10. Fellows, M., Downey, R., Kapron, B., Hallett, M., and Wareham, H. T. The parameterized complexity of some problems in logic and linguistics. In Proceedings of Symposium on Logical Foundations of Computer Science (LFCS) (1994), vol. 813 of Lecture Notes in Computer Science, Springer-Verlag, pp. 89 – 100. [ bib ]
  11. Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Combinatorial Pattern Matching, 5th Annual Symposium, CPM’94 (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 15-30. [ bib ]

 

1993
  1. Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and well-quasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539-564. [ bib ]
  2. Abrahamson, K., Downey, R., and Fellows, M. R. Fixed-parameter intractability II. In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Sciences, STACS’93(1993), vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pp. 374-385. [ bib ]
  3. Fellows, M. R., Hallett, M. T., and Wareham, H. T. DNA physical mapping: Three ways difficult. In Proceedings of the 1st Annual European Symposium on Algorithms, ESA ’93, T. Lengauer, Ed., vol. 726 of Lecture Notes in Computer Science. Springer-Verlag, 1993, pp. 157-168. [ bib ]
  4. Downey, R., and Fellows, M. Fixed-parameter tractability and completeness III: Some structural aspects of the W hierarchy. In Complexity Theory: Current Research – Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity (Cambridge, 1993), K. Ambos-Spies, S. Homer, and U. Schöning, Eds., Cambridge University Press, pp. 191-225. [ bib ]
  5. Abrahamson, K. A., Downey, R. G., and Fellows, M. R. Fixed-parameter intractability II. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS’93 (1993), P. Enjalbert, A. Finkel, and K. W. Wagner, Eds., vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pp. 374-385. [ bib ]
  6. Fellows, M. R., and Koblitz, N. Fixed-parameter complexity and cryptography. In Proceedings of 10th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC’93, San Juan de Puerto Rico, Puerto Rico (1993), G. D. Cohen, T. Mora, and O. Moreno, Eds., vol. 673 of Lecture Notes in Computer Science, Springer, pp. 121-131. [ bib ]
  7. Downey, R. G., Evans, P. A., and Fellows, M. R. Parameterized learning complexity. In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory(1993), ACM Press, pp. 51-57. [ bib | pdf ]
  8. Fellows, M., and Koblitz, N. Kid krypto. In Proceedings of Crypto 1992 (1993), vol. 740 of Lecture Notes in Computer Science, Springer-Verlag, New York, Inc., p. 371—389. [ bib | pdf ]
  9. Fellows, M. Computer science in the elementary schools. In Proceedings of the Mathematicians and Education Reform Workshop, Seattle, 1991 (1993), N. Fisher, H. Keynes, and P. Wagreich, Eds., vol. 3 of Issues in Mathematics Education, Conference Board of the Mathematical Sciences, p. 143 –163. [ bib | pdf ]
  10. Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and well-quasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539-564. [ bib ]

 

1992
  1. Casey, N., and Fellows, M. R. This is Mega-Mathematics! Los Alamos National Labs, 1992. Available at http://www.c3.lanl..gov/ captors/mega-math. See also http://www.ccs3.lanl.gov/mega-math/write.html. [ bib ]
  2. Fellows, M. R., and Langston, M. A. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117-126. [ bib ]
  3. Bodlaender, H. L., Fellows, M. R., and Warnow, T. J. Two strikes against perfect phylogeny. In Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP’92 (1992), W. Kuich, Ed., vol. 623 of Lecture Notes in Computer Science, Springer-Verlag, pp. 273-283. [ bib | pdf ]
  4. Downey, R., and Fellows, M. Fixed-parameter intractability. In Proceedings of the Seventh Annual IEEE Conference on Structure in Complexity Theory (1992), pp. 36-49. [ bib ]
  5. Downey, R., and Fellows, M. Fixed-parameter tractability and completeness. Congressus Numerantium 87 (1992), 161-178. [ bib ]
  6. Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and prime factorization. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT’92 (1992), IEEE Computer Society Press, pp. 107-110. [ bib | pdf ]
  7. Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and prime factorization. Designs, Codes and Cryptography 2, 3 (1992), 231-235. [ bib ]
  8. Casey, N., and Fellows, M. R. This is Mega-Mathematics! Los Alamos National Labs, 1992. Available at http://www.c3.lanl.gov/ captors/mega-math. See also http://www.ccs3.lanl.gov/mega-math/write.html. [ bib | pdf ]
  9. Fellows, M. R., and Langston, M. A. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117-126. [ bib ]
  10. Campbell, L., Carlsson, G. E., Dinneen, M. J., Faber, V., Fellows, M., Langston, M. A., Moore, J. W., Mullhaupt, A. P., and Sexton, H. B. Small diameter symmetric networks from linear groups. IEEE Transactions on Computers 40 (1992), 218-220. [ bib ]
  11. Abrahamson, K. R., Fellows, M. R., and Wilson, C. B. Parallel self-reducibility. In Proceedings of Computing and Information ICCI’92, Fourth International Conference on Computing and Information (1992), W. W. Koczkodaj, P. E. Lauer, and A. A. Toptsis, Eds., IEEE Computer Society, pp. 67-70. [ bib ]
  12. Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and certificates for primality. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT’92 (1992), IEEE Computer Society Press, pp. 107-110. [ bib | pdf ]

 

1991
  1. Dinneen, M. J., Fellows, M. R., and Faber, V. Algebraic constructions of efficient broadcast networks. In Proceedings of Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC’91 (Berlin, Germany, 1991), H. F. Mattson, T. Mora, and T. R. N. Rao, Eds., vol. 539 of LNCS, Springer-Verlag, pp. 152-158. [ bib ]
  2. Abello, Fellows, and Stillwell. On the complexity and combinatorics of covering finite complexes. AJC: Australasian Journal of Combinatorics 4 (1991), 103-112. [ bib ]
  3. Fellows, M. R., and Kaschube, P. A. Searching for k3,3 in linear time. Linear and Multilinear Algebra 29, 3 (1991), 279-290. [ bib ]
  4. Fellows, M. R., and Hoover, M. Perfect domination. AJC: Australasian Journal of Combinatorics 3 (1991), 141-150. [ bib ]
  5. Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87-101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. [ bib ]
  6. Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87-101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. [ bib ]
  7. Dinneen, M., Faber, V., and Fellows, M. Algebraic constructions of efficient broadcast networks. In Proceedings of the Ninth International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC’91) (1991), H. F. Mattson, T. Mora, and T. Rao, Eds., vol. 539 of Lecture Notes in Computer Science, Springer-Verlag, pp. 152-158. [ bib ]
  8. Abrahamson, K., Fellows, M. R., Langston, M. A., and Moret, B. M. E. Constructive complexity. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 34 (1991), 3-16. [ bib ]
  9. Fellows, M. R., and Langston, M. A. Fast search algorithms for layout permutation problems. Integration, the VLSI Journal 12, 3 (1991), 321 – 337. [ bib ]

 

1990
  1. Fellows, M., and Kleitman, D. J. Transversals of vertex partitions in graphs. SIAM Journal of Discrete Mathematics 3 (1990), 206-215. [ bib ]

 

1989
  1. Fellows, M. R. The Robertson-Seymour theorems: A survey of applications. In CMGA: Graphs and Algorithms: Contemporary Mathematics (1989), vol. 89, AMS, pp. 1-18. [ bib ]
  2. Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31(1989), 1-9. [ bib ]
  3. Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32. [ bib ]
  4. Fellows, M., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS’89 (1989), IEEE Computer Society Press, pp. 520-525. [ bib ]
  5. Fellows, M., Kinnersley, N., and Langston, M. Finite-basis theorems and a computation-integrated approach to obstruction set isolation. In Proceedings of the Third Conference on Computers and Mathematics (1989), E. Kaltofen and S. M. Watt, Eds., Springer-Verlag, pp. 37-45. [ bib ]
  6. Fellows, M. R., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS’89 (1989), IEEE Computer Society Press, pp. 520-525. [ bib | pdf ]
  7. Abrahamson, K. R., Fellows, M. R., Ellis, J. A., and Mata, M. E. On the complexity of fixed parameter problems. In Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS’89 (1989), IEEE Computer Society Press, pp. 210-215. [ bib | pdf ]
  8. Fellows, M. R., and Wojciechowski, J. M. Counting spanning trees in directed regular multigraphs. Journal of the Franklin Institute 326 (1989), 889-896. [ bib ]
  9. Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31(1989), 1-9. [ bib ]
  10. Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32. [ bib ]
  11. Fellows, M., and Kleitman, D. J. Radius and diameter in manhattan lattices. Discrete Mathematics 73 (1989), 119-125. [ bib ]
  12. Fellows, M., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS’89 (Research Triangle Park, NC) (1989), IEEE Computer Society Press, pp. 520-525. [ bib ]
  13. Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomial-time algorithms. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC’89 (1989), ACM SIGACT, ACM Press, pp. 501-512. [ bib | pdf ]

 

1988
  1. Fellows, M. R., and Langston, M. A. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM 35, 3 (1988), 727-739. [ bib | pdf ]
  2. Fellows, M. R., and Langston, M. A. Layout permutation problems and well-partially-ordered sets. In Proceedings of the fifth MIT conference on Advanced research in VLSI(Cambridge, MA, USA, 1988), MIT Press, pp. 315-327. [ bib ]
  3. Fellows, M. R., and Langston, M. A. Fast self-reduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC’88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of Lecture Notes in Computer Science, Springer-Verlag, pp. 278-287. [ bib ]
  4. Fellows, M. R., Friesen, D. K., and Langston, M. A. On finding optimal and near-optimal lineal spanning trees. Algorithmica 3, 4 (1988), 549-560. [ bib ]
  5. Fellows, M., Hoover, M., and Harary, F. On the galactic number of a hypercube. Mathematical and Computer Modelling 11 (1988), 212 – 215. [ bib ]
  6. Fellows, M., and Langston, M. A. Processor utilization in a linearly connected parallel processing system. IEEE Transactions on Computers 37 (1988), 594 – 603. [ bib ]
  7. Fellows, M. R., and Langston, M. A. Fast self-reduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC’88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of LNCS, Springer-Verlag, pp. 278-287. [ bib ]

 

1987
  1. Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162. [ bib ]
  2. R. L. Bryant, N. G. Kinnersley, M. R. F., and Langston, M. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397-398. [ bib ]
  3. Bryant, R. L., Fellows, M. R., Kinnersley, N. G., and Langston, M. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397-398. [ bib ]
  4. Fellows, M., Hickling, F., and Syslo, M. A topological parameterization and hard graph problems. Congressus Numerantium 59 (1987), 69-78. [ bib ]
  5. Clark, L. H., Entringer, R. C., and Fellows, M. Computational complexity of integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 2 (1987), 179-191. [ bib ]
  6. Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162. [ bib ]