Publications and papers

Links to the Postprint versions of the published papers are also included here (with permission from the relevant publishers) for those who do not have online access to the relevant journals / conference proceedings.

Book chapter

Edited journal issue

Journal papers

  1. “Almost stable” matchings in the Roommates problem with bounded lists, with Péter Biró and Eric McDermid.  Theoretical Computer Science, 432 : 10-20, 2012.
  2. An algorithm for a super-stable roommates problem, with Tamás Fleiner and Rob Irving.  Theoretical Computer Science, 412 (50) : 7059-7065, 2011.  Postprint.
  3. The College Admissions Problem with Lower and Common Quotas, with Péter Biró, Tamás Fleiner and Rob Irving.  Theoretical Computer Science, 411 : 3136-3153, 2010.  The full version of this paper is available as Technical Report no. TR-2009-303, Department of Computing Science, University of Glasgow, 2009.  Postprint.
  4. Keeping partners together: Algorithmic results for the Hospitals / Residents problem with couples, with Eric McDermid.  Journal of Combinatorial Optimization, 19 (3) : 279-303, 2010.  Postprint.
  5. Size versus stability in the Marriage problem, with Péter Biró and Shubham Mittal.  Theoretical Computer Science, 411 : 1828-1841, 2010.  Postprint.
  6. Popular matchings in the weighted capacitated house allocation problem (journal version), with Colin Sng.  Journal of Discrete Algorithms, 8:102-116, 2010.  Postprint.
  7. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs, with Péter Biró and Romeo Rizzi.  Discrete Mathematics, Algorithms and Applications, 1 (4) : 499-517, 2009.  Postprint.
  8. Finding large stable matchings, with Rob Irving.  ACM Journal of Experimental Algorithmics, volume 14, section 1, article 2, 30 pages, 2009.  Postprint.
  9. Vertex and edge covers with clustering properties: complexity and algorithms, with Henning Fernau.  Journal of Discrete Algorithms, 7 (2) : 149-167, 2009.  Postprint.
  10. Stable marriage with ties and bounded length preference lists, with Rob Irving and Gregg O’Malley.  Journal of Discrete Algorithms, 7 (2) : 213-219, 2009.  Postprint.
  11. The Stable Roommates problem with Globally-Ranked Pairs, with David Abraham, Ariel Levavi and Gregg O’Malley.  Internet Mathematics 5(4):493-515, 2008.  Postprint.
  12. The Stable Marriage Problem with Master Preference Lists, with Rob Irving and Sandy Scott.  Discrete Applied Mathematics, 156 (15) : 2959-2977, 2008.  Postprint.
  13. Student-project allocation with preferences over projects, with Gregg O’Malley.  Journal of Discrete Algorithms, 6 : 553-560, 2008.  Postprint.
  14. Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems, with Rob Irving.  Journal of Combinatorial Optimization, 16 (3) : 279-292, 2008.  Postprint.
  15. Efficient algorithms for generalized stable marriage and roommates problems, with Tamás Fleiner and Rob Irving.  Theoretical Computer Science, 381 (1-3) : 162-176, 2007.  Postprint.
  16. Two algorithms for the Student-Project Allocation problem, with David Abraham and Rob Irving.  Journal of Discrete Algorithms, 5 (1) :73-90, 2007.  Postprint.
  17. The Exchange-Stable Marriage Problem, with Katarína Cechlárová.  Discrete Applied Mathematics, 152 (1-3) : 109-122, 2005.  Postprint.
  18. On the approximability of the maximum induced matching problem, with William Duckworth and Michele Zito.  Journal of Discrete Algorithms, 3(1):79-91, 2005.  Postprint.
  19. Combined Super-/Substring and Super-/Subsequence Problems, with Martin Middendorf.  Theoretical Computer Science, 320 (2-3) : 247-267, 2004.  Postprint.
  20. Approximability results for stable marriage problems with ties, with Magnús Halldórsson, Rob Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita and Sandy Scott.  Theoretical Computer Science, 306 (1-3) : 431-447, 2003.  Postprint.
  21. The Stable Roommates Problem with Ties, with Rob Irving.  Journal of Algorithms, 43:85-105, 2002.  Errata.  Postprint.
  22. Hard variants of stable marriage, with Rob Irving, Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita.  Theoretical Computer Science, 276 (1-2) : 261-279, 2002.  Postprint.
  23. The structure of stable marriage with indifference.  Discrete Applied Mathematics, 122 (1-3) : 167-181, 2002.  Postprint.
  24. On the algorithmic complexity of twelve covering and independence parameters of graphs.  Discrete Applied Mathematics, 91 (1-3) : 155-175, 1999.  Postprint.
  25. The b-chromatic number of a graph, with Rob Irving.  Discrete Applied Mathematics, 91 (1-3) : 127-141, 1999.  Postprint.

Conference papers

  1. Paired and altruistic kidney donation in the UK: Algorithms and experimentation, with Gregg O’Malley.  In Proceedings of SEA 2012: the 11th International Symposium on Experimental Algorithms, volume 7276 of Lecture Notes in Computer Science, pages 271-282, Springer, 2012.  The full version of this paper is available as Technical Report no. TR-2012-330, School of Computing Science, University of Glasgow, 2012.
  2. Popular matchings in the Marriage and Roommates problems, with Péter Biró and Rob Irving.  In Proceedings of CIAC 2010: the 7th International Conference on Algorithms and Complexity, volume 6078 of Lecture Notes in Computer Science, pages 97-108, Springer, 2010.  Postprint.  The full version of this paper is available as Technical Report no. TR-2009-306, Department of Computing Science, University of Glasgow, 2009.
  3. Size versus stability in the Marriage problem, with Péter Biró and Shubham Mittal.  In Proceedings of WAOA 2008: the 6th Workshop on Approximation and Online Algorithms, volume 5426 of Lecture Notes in Computer Science, pages 15-28, Springer, 2009.  Postprint.  The full version of this paper is available as Technical Report no. TR-2009-297, Department of Computing Science, University of Glasgow, 2009.
  4. The Stable Roommates problem with Globally-Ranked Pairs, with David Abraham, Ariel Levavi and Gregg O’Malley.  In Proceedings of WINE 2007: the 3rd International Workshop On Internet and Network Economics, volume 4858 of Lecture Notes in Computer Science, pages 431-444, Springer, 2007.  Postprint.  The full version of this paper is available as Technical Report no. TR-2007-257, Department of Computing Science, University of Glasgow, 2007.
  5. An 8/5-approximation algorithm for a hard variant of stable marriage, with Rob Irving.  In Proceedings of COCOON 2007: the 13th Annual International Computing and Combinatorics Conference, volume 4598 of Lecture Notes in Computer Science, pages 548–558, Springer, 2007.  Postprint.  Note: there is a mistake in the COCOON paper.  The correct performance guarantee for the approximation algorithm is 5/3.  See the full version of the paper, in Journal of Combinatorial Optimization, 16 (3) : 279-292, 2008.
  6. A Constraint Programming Approach to the Hospitals / Residents Problem, with Gregg O’Malley, Patrick Prosser and Chris Unsworth.  In Proceedings of CP-AI-OR 2007: the Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 4510 of Lecture Notes in Computer Science, pages 155-170, Springer, 2007.  Postprint.  The full version of this paper is available as Technical Report no. TR-2007-236, Department of Computing Science, University of Glasgow, 2007.
  7. Popular matchings in the Capacitated House Allocation problem, with Colin Sng.  In Proceedings of ESA 2006: the 14th Annual European Symposium on Algorithms, volume 4168 of Lecture Notes in Computer Science, pages 492-503, Springer, 2006.  Postprint.  The full version of this paper is available as Technical Report no. TR-2006-222, Department of Computing Science, University of Glasgow, 2006.
  8. “Almost stable” matchings in the Roommates problem, with David Abraham and Péter Biró.  In Proceedings of WAOA 2005: the 3rd Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science, pages 1-14, Springer, 2006.  Postprint.
  9. Pareto Optimality in House Allocation Problems, with David Abraham, Katarína Cechlárová and Kurt Mehlhorn.  In Proceedings of ISAAC 2004: the 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 3-15, Springer, 2004.  Postprint.  Some fonts were missing in the printing of the hard-copy version (but not the on-line version) of this paper.  Springer printed a corrected version in Proceedings of ISAAC 2005: the 16th Annual International Symposium on Algorithms and Computation, volume 3827 of Lecture Notes in Computer Science, pages 1163-1175, Springer, 2005.
  10. The Student-Project Allocation Problem, with David Abraham and Rob Irving. In Proceedings of ISAAC 2003: the 14th Annual International Symposium on Algorithms and Computation, volume 2906 of Lecture Notes in Computer Science, pages 474-484, Springer, 2003.  Postprint.  The full version of this paper appeared in Journal of Discrete Algorithms, 5 (1) :73-90, 2007.
  11. Strong Stability in the Hospitals / Residents Problem, with Rob Irving and Sandy Scott. In Proceedings of STACS 2003: the 20th International Symposium on Theoretical Aspects of Computer Science, volume 2607 of Lecture Notes in Computer Science, pages 439-450, Springer, 2003.  Postprint.  The full version of this paper is available as Technical Report no. TR-2002-123, Department of Computing Science, University of Glasgow, 2002 (revised May 2005).
  12. A Constraint Programming Approach to the Stable Marriage Problem, with Ian Gent, Rob Irving, Patrick Prosser and Barbara Smith. In Proceedings of CP '01: the 7th International Conference on Principles and Practice of Constraint Programming, volume 2239 of Lecture Notes in Computer Science, pages 225-239, Springer, 2001.  Postprint.
  13. The Hospitals/Residents Problem with Ties, with Rob Irving and Sandy Scott. In Proceedings of SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 259-271. Springer, 2000.  Postprint.
  14. Stable marriage with incomplete lists and ties, with Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita. In Proceedings of ICALP '99: the 26th International Colloquium on Automata, Languages and Programming, volume 1644 of Lecture Notes in Computer Science, pages 443-452. Springer, 1999.  Postprint.

Workshop papers

  1. An algorithm for a super-stable roommates problem, with Tamás Fleiner and Rob Irving.  In Proceedings of Match-UP: Matching Under Preferences – Algorithms and Complexity, held at ICALP 2008, pages 126-132.
  2. Popular matchings in the weighted capacitated house allocation problem, with Colin Sng.  In Proceedings of ACiD 2007: the 3rd Algorithms and Complexity in Durham workshop, volume 9 of Texts in Algorithmics, pages 129-140, College Publications, 2007.  The full version of this paper is available as Technical Report no. TR-2007-254, Department of Computing Science, University of Glasgow, 2007.
  3. Stable marriage with ties and bounded length preference lists, with Rob Irving and Gregg O’Malley.  In Proceedings of ACiD 2006: the 2nd Algorithms and Complexity in Durham workshop, volume 7 of Texts in Algorithmics, pages 95-106, College Publications, 2006.
  4. Vertex and edge covers with clustering properties: complexity and algorithms, with Henning Fernau.  In Proceedings of ACiD 2006: the 2nd Algorithms and Complexity in Durham workshop, volume 7 of Texts in Algorithmics, pages 69-84, College Publications, 2006.  The full version of this paper is available as Technical Report no. TR-2006-210, Department of Computing Science, University of Glasgow, 2006.
  5. The Kidney Exchange Game, with Katarína Cechlárová and Tamás Fleiner.  In Proceedings of SOR ’05: the 8th International Symposium on Operations Research in Slovenia, pages 77-83, 2005.  IM Preprint series A, no. 5/2005, PJ Šafárik University, Faculty of Science, Institute of Mathematics.
  6. A Constraint Programming Approach to the Hospitals / Residents Problem, with Gregg O’Malley, Patrick Prosser and Chris Unsworth.  In Proceedings of the Fourth Workshop on Modelling and Reformulating Constraint Satisfaction Problems, held at CP ’05, pages 28-43, 2005.  The full version of this paper is available as Technical Report no. TR-2005-196, Department of Computing Science, University of Glasgow, 2005.
  7. Modelling and solving the stable marriage problem using constraint programming, with Gregg O’Malley.  In Proceedings of the Fifth Workshop on Modelling and Solving Problems with Constraints, held at IJCAI ’05, pages 10-17, 2005.  The full version of this paper is available as Technical Report no. TR-2005-192, Department of Computing Science, University of Glasgow, 2005.
  8. Student-project allocation with preferences over projects, with Gregg O’Malley.  In Proceedings of ACiD 2005: the 1st Algorithms and Complexity in Durham workshop, volume 4 of Texts in Algorithmics, pages 69-80, KCL Publications, 2005.

In submission

Technical reports (not superseded by the above)

PhD thesis

Other papers