Dr David Manlove
- Senior Lecturer (Computing Science)
telephone: 01413302794
email: David.Manlove@glasgow.ac.uk
Personal site: http://www.dcs.gla.ac.uk/~davidm
Biography:
Dr David Manlove is a Senior Lecturer at the School of Computing Science, University of Glasgow. He joined the academic staff in October 2000, and held a Royal Society of Edinburgh / Scottish Government Personal Research Fellowship from October 2003 to September 2006. His research interests lie mainly in the area of algorithms and complexity.
Prior to starting as a lecturer, Dr Manlove was a Research Assistant, working on an EPSRC research project with Dr Rob Irving. He obtained his PhD in Computing Science from the University of Glasgow in 1998, working under the supervision of Dr Irving. Previously, he obtained a BA in Mathematics and Computation from the University of Oxford in 1995 (MA in 2000).
Dr Manlove is a Fellow of the Higher Education Academy and was elected as Secretary of the British Colloquium for Theoretical Computer Science (2011-2014). Within the School, he is a member of the Formal Analysis, Theory and Algorithms research group.
Research Interests:
- Algorithms and Complexity
- Matching problems with and without preferences
- Algorithms for applications of matching problems: kidney exchange,
allocation of junior doctors to hospitals, school placement, student-project allocation
- Algorithmic graph theory
- Colouring, independence and domination in graphs
- Complexity and approximability of optimisation problems
2013
Askalidis, G., Immorlica, N., Kwanashie, A., Manlove, D.F., and Pountourakis, E. (2013) Socially stable matchings in the hospitals / residents problem. Lecture Notes in Computer Science, 8037 . pp. 85-96. ISSN 0302-9743 (doi:10.1007/978-3-642-40104-6_8)
Harrenstein, P., Manlove, D., and Wooldridge, M. (2013) The joy of matching. IEEE Intelligent Systems, 28 (2). pp. 81-85. ISSN 1541-1672 (doi:10.1109/MIS.2013.49)
Manlove, D. (2013) Algorithmics Of Matching Under Preferences. Series: Theoretical Computer Science . World Scientific Publishing. ISBN 9789814425247
2012
Biró, P., Manlove, D.F., and McDermid, E.J. (2012) "Almost stable" matchings in the roommates problem with bounded preference lists. Theoretical Computer Science, 432 . pp. 10-20. ISSN 0304-3975 (doi:10.1016/j.tcs.2012.01.022)
Manlove, D.F., and O’Malley, G. (2012) Paired and altruistic kidney donation in the UK: algorithms and experimentation. Lecture Notes in Computer Science, 7276 . pp. 271-282. ISSN 0302-9743 (doi:10.1007/978-3-642-30850-5_24)
2011
Fleiner, T., Irving, R.W., and Manlove, D.F. (2011) An algorithm for a super-stable roommates problem. Theoretical Computer Science, 421 (50). pp. 7059-7065. ISSN 0304-3975 (doi:10.1016/j.tcs.2011.09.012)
2010
Manlove, D., Irving, R., and Iwama, K. (2010) Guest editorial: special issue on matching under preferences. Algorithmica, 58 (1). pp. 1-4. ISSN 0178-4617 (doi:10.1007/s00453-010-9415-z)
Sng, C.T.S., and Manlove, D.F. (2010) Popular matchings in the weighted capacitated house allocation problem. Journal of Discrete Algorithms, 8 (2). pp. 102-116. ISSN 1570-8667 (doi:10.1016/j.jda.2008.11.008)
McDermid, E.J., and Manlove, D.F. (2010) Keeping partners together: algorithmic results for the hospitals/residents problem with couples. Journal of Combinatorial Optimization, 19 (3). pp. 279-303. ISSN 1382-6905 (doi:10.1007/s10878-009-9257-2)
Biro, P., Manlove, D.F., and Mittal, S. (2010) Size versus stability in the marriage problem. Theoretical Computer Science, 411 (16-18). pp. 1828-1841. ISSN 0304-3975 (doi:10.1016/j.tcs.2010.02.003)
Biro, P., Fleiner, T., Irving, R.W., and Manlove, D.F. (2010) The College Admissions problem with lower and common quotas. Theoretical Computer Science, 411 (34-36). pp. 3136-3153. ISSN 0304-3975 (doi:10.1016/j.tcs.2010.05.005)
Biró, P., Irving, R., and Manlove, D.F. (2010) Popular matchings in the marriage and roommates problems. Lecture Notes in Computer Science, 6078 . pp. 97-108. ISSN 0302-9743 (doi:10.1007/978-3-642-13073-1_10)
Manlove, D.F., Irving, R.W., and Iwama, K. (2010) Special issue on matching under preferences. Algorithmica, 58 (1). p. 1. ISSN 0178-4617 (doi:10.1007/s00453-010-9415-z)
2009
Biro, P., Manlove, D.F., and Rizzi, R. (2009) Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1 (4). pp. 499-517. ISSN 1793-8309 (doi:10.1142/S1793830909000373)
Irving, R.W., and Manlove, D.F. (2009) Finding large stable matchings. Journal of Experimental Algorithmics, 14 . 1.2. ISSN 1084-6654 (doi:10.1145/1498698.1537595)
Fernau, H., and Manlove, D.F. (2009) Vertex and edge covers with clustering properties: complexity and algorithms. Journal of Discrete Algorithms, 7 (2). pp. 149-167. ISSN 1570-8667 (doi:10.1016/j.jda.2008.09.007)
Irving, R.W., Manlove, D.F., and O'Malley, G. (2009) Stable marriage with ties and bounded length preference lists. Journal of Discrete Algorithms, 7 (2). pp. 213-219. ISSN 1570-8667 (doi:10.1016/j.jda.2008.09.003)
Biro, P., Manlove, D.F., and Mittal, S. (2009) Size versus stability in the marriage problem. In: Approximation and Online Algorithms. Springer, pp. 15-28. ISBN 9783540939795
2008
Manlove, D.F., and O'Malley, G. (2008) Student-project allocation with preferences over projects. Journal of Discrete Algorithms, 6 (4). pp. 553-560. ISSN 1570-8667 (doi:10.1016/j.jda.2008.07.003)
Irving, R.W., and Manlove, D.F. (2008) Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems. Journal of Combinatorial Optimization, 16 (3). pp. 279-292. ISSN 1382-6905 (doi:10.1007/s10878-007-9133-x)
Irving, R.W,, Manlove, D.F., and Scott, S. (2008) The stable marriage problem with master preference lists. Discrete Applied Mathematics, 156 (15). pp. 2959-2977. ISSN 0166-218X (doi:10.1016/j.dam.2008.01.002)
Abraham, D.J., Levavi, A., Manlove, D.F., and O'Malley, G. (2008) The stable roommates problem with globally-ranked pairs. Internet Mathematics, 5 (4). pp. 493-515. ISSN 1542-7951
Manlove, D.M. (2008) Hospitals/residents problem. In: Kao, M-Y. (ed.) Encyclopedia of Algorithms. Springer, pp. 390-394. ISBN 9780387301624
2007
Fleiner, T., Irving, R.W., and Manlove, D.F. (2007) Efficient algorithms for generalized Stable Marriage and Roommates problems. Theoretical Computer Science, 381 (1-3). pp. 162-176. ISSN 0304-3975 (doi:10.1016/j.tcs.2007.04.029)
Irving, R.W., and Manlove, D.F. (2007) An 8/5 approximation algorithm for a hard variant of stable marriage. In: Proceedings of COCOON 2007, 13th Annual International Computing and Combinatorics Conference, 16-19 July 2007, Banff, Canada.
Manlove, D.M., O'Malley, G., Prosser, P., and Unsworth, C. (2007) A constraint programming approach to the hospitals/residents problem. In: Proceedings of CP-AI-OR '07: the Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 23-26 May, 2007, Brussels, Belgium.
Abraham, D.J., Irving, R.W., and Manlove, D.M. (2007) Two algorithms for the student-project allocation problem. Journal of Discrete Algorithms, 5 (1). pp. 73-90. ISSN 1570-8667 (doi:10.1016/j.jda.2006.03.006)
2006
Manlove, D.F., and Sng, C.T.S. (2006) Popular Matchings in the Capacitated House Allocation Problem. In: Proceedings of ESA 2006: the 14th Annual European Symposium on Algorithms, 11-13 September 2006, Zurich, Switzerland.
Abraham, D.J., Biro, P., and Manlove, D.F. (2006) "Almost stable" matchings in the Roommates problem. In: Proceedings of WAOA 2005: the 3rd International Workshop on Approximation and Online Algorithms, 6-7 October, 2005, Palma, Mallorca.
2005
Cechlarova, K., and Manlove, D.F. (2005) The exchange-stable marriage problem. Discrete Applied Mathematics, 152 (1-3). pp. 109-122. ISSN 0166-218X (doi:10.1016/j.dam.2005.06.003)
Duckworth, W., Manlove, D.F., and Zito, M. (2005) On the approximability of the maximum induced matching problem. Journal of Discrete Algorithms, 3 (1). pp. 79-91. ISSN 1570-8667 (doi:10.1016/j.jda.2004.05.001)
2004
Middendorf, M., and Manlove, D.F. (2004) Combined super-/substring and super-/subsequence problems. Theoretical Computer Science, 320 (2-3). pp. 247-267. ISSN 0304-3975 (doi:10.1016/j.tcs.2004.02.001)
Abraham, D.J., Cechlarova, K., Manlove, D.F., and Mehlhorn, K. (2004) Pareto optimality in house allocation problems. In: Proceedings of ISAAC 2004: the 15th Annual International Symposium on Algorithms and Computation, 20-22 December, 2004, Hong Kong.
2003
Halldorsson, M., Irving, R.W., Iwama, K., Manlove, D. F., Miyazaki, S., Morita, Y., and Scott, S. (2003) Approximability results for stable marriage problems with ties. Theoretical Computer Science, 306 (1-3). pp. 431-447. ISSN 0304-3975 (doi:10.1016/S0304-3975(03)00321-9)
Abraham, D.J., Irving, R.W., and Manlove, D.F (2003) The student-project allocation problem. In: Proceedings of ISAAC 2003: the 14th Annual International Symposium on Algorithms and Computation, 15-17 December, 2003, Kyoto, Japan.
Irving, R.W, Manlove, D.F., and Scott, S. (2003) Strong stability in the Hospitals/Residents problem. In: Proceedings of STACS 2003: the 20th International Symposium on Theoretical Aspects of Computer Science, 27 February - 1 March, 2003, Berlin, Germany.
2002
Irving, R. W., and Manlove, D.F. (2002) The stable roommates problem with ties. Journal of Algorithms, 43 (1). pp. 85-105. ISSN 0196-6774 (doi:10.1006/jagm.2002.1219)
Manlove, D.F. (2002) The structure of stable marriage with indifference. Discrete Applied Mathematics, 122 (1-3). pp. 167-181. ISSN 0166-218X (doi:10.1016/S0166-218X(01)00322-5)
Manlove, D.F., Irving, R. W., Iwama, K., Miyazaki, S., and Morita, Y. (2002) Hard variants of stable marriage. Theoretical Computer Science, 276 (1-2). pp. 261-279. ISSN 0304-3975 (doi:10.1016/S0304-3975(01)00206-7)
2001
Gent, I. P., Irving, R.W., Manlove, D.F., Prosser, P., and Smith, B.M. (2001) A constraint programming approach to the stable marriage problem. In: Proceedings of CP '01: the 7th International Conference on Principles and Practice of Constraint Programming, 26 November - 1 December, 2001, Paphos, Cyprus.
2000
Irving, R. W, Manlove, D.F., and Scott, S. (2000) The hospitals/residents problem with ties. In: Proceedings of SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory, 5-7 July, 2000, Bergen, Norway.
1999
Irving, R.W., and Manlove, D.F. (1999) The b-chromatic number of a graph. Discrete Applied Mathematics, 91 (1-3). pp. 127-141. ISSN 0166-218X (doi:10.1016/S0166-218X(98)00146-2)
Iwama, K., Manlove, D.F., Miyazaki, S., and Morita, Y. (1999) Stable marriage with incomplete lists and ties. In: Proceedings of ICALP '99: the 26th International Colloquium on Automata, Languages and Programming, 11-15 July, 1999, Prague, Czech Republic.
Manlove, D.F. (1999) On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Applied Mathematics, 91 (1-3). pp. 155-175. ISSN 0166-218X (doi:10.1016/S0166-218X(98)00147-4)