Catherine McCartin

Senior Lecturer, School of Engineering and Advanced Technology

Publications

Journal Articles

• A 3-approximation Algorithm for the Subtree Distance Between Phylogenies
  Magnus Bordewich, Catherine McCartin and Charles Semple
  in Journal of Discrete Algorithms 6(3), pp 458-471, 2008.
• Parameterized approximation of dominating set problems
  Rodney G. Downey, Michael R. Fellows, Catherine McCartin, Frances A. Rosamond
  in Information Processing Letters 109(1), pp 68-70, 2008.
• On the Parameterized Complexity of Layered Graph Drawing
  Dujmovic, V., Fellows, M. R., Kitching, M., Liotta, G., McCartin, C. M., Nishimura, N., Ragde, P., Rosamond, F. A., Whitesides, S., Wood, D. R.
  in Algorithmica 52(2), pp 267-292, 2008.
• A Faster FPT Algorithm for the Maximum Agreement Forest Problem.
  Michael T. Hallett and Catherine McCartin
  in Theory of Computing Systems 6(3), 41 (3), pp 539-550, 2007.
• Online Promise Problems with Online Width Metrics
  Rodney G. Downey and Catherine McCartin
  in Journal of Computer and System Sciences 73, pp 57-72, 2007.
• A Fixed-Parameter Approach to Two-Layer Planarization
  Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C. M., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., Wood, D. R.
  in Algorithmica 45 (2), pp 159-182, 2006.
• Parameterized Counting Problems
  in Annals of Pure and Applied Logic 138, pp 147-182, 2006.
  (RSNZ Hatherton Award winning paper, 2006.)
• On the Parametric Complexity of Schedules to Minimize Tardy Tasks
  Michael R. Fellows and Catherine McCartin
  in Theoretical Computer Science 298, pp 317-324, 2003.
• An Improved Algorithm for the Jump Number Problem
  in Information Processing Letters 79, pp 87-92, 2001.

Book Chapter

• Basic Complexity (with Eric Allender),
  in Aspects of Complexity
  (ed. Downey and Hirschfeldt), de Gruyter Series in Logic and Its Applications, Volume 4, 2001.

Refereed Conference Proceedings

• Parameterized Approximation Problems. (with Rodney G. Downey and Michael R. Fellows),
  in Proceedings of IWPEC 2006,
  Lecture Notes in Computer Science 4169, pp 121-129, 2006.
• Bounded Persistence Pathwidth (with Rodney G. Downey),
  in Proceedings of CATS 2005, Computing, The Australasian Theory Symposium,
  Conferences in Research and Practice in Information Technology, Vol 41, pp 51-56, 2005.
• Some New Directions and Questions in Parameterized Complexity (with Rodney G. Downey),
  in Proceedings of DLT04,
  Lecture Notes in Computer Science 3340, pp 12-26, 2004.
• Online Problems, Pathwidth, and Persistence (with Rodney G. Downey),
  in Proceedings of IWPEC 2004,
  Lecture Notes in Computer Science 3162, pp 13-24, 2004.
• Parameterized Counting Problems
  in Proceedings of Mathematical Foundations of Computer Science 2002,
  Lecture Notes in Computer Science 2420, pp 556-567, 2002.
• A Fixed-Parameter Approach to Two-Layer Planarization
  (with the participants of the International Workshop on Fixed Parameter Tractability in Graph Drawing,
  Bellaires Research Institute of McGill University, Barbados),
  in Proceedings of 9th International Symposium on Graph Drawing,
  Lecture Notes in Computer Science 2265, pp 1-15, 2002.
• On the Paramaterized Complexity of Layered Graph Drawing
  (with the participants of the International Workshop on Fixed Parameter Tractability in Graph Drawing,
  Bellaires Research Institute of McGill University, Barbados),
  in Proceedings of 9th Annual European Symposium on Algorithms,
  Lecture Notes in Computer Science 2161, pp 488-499, 2001.
• Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems
  (with Michael R. Fellows, Frances A. Rosamund, and Ulrike Stege),
  in Proceedings of FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science 20th Conference,
  Lecture Notes in Computer Science, Volume 1974, pp.240-251, December 2000.

• PhD Thesis (2003)