Rob Irving - Publications

Books and book chapters

-        R.W. Irving, The stable marriage problem, Article 142 in The Encyclopedia of Algorithms, Springer 2008.

-        R.W. Irving, Optimal stable marriage, Article 143 in The Encyclopedia of Algorithms, Springer 2008.

-        D. Gusfield & R.W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Boston, Ma., 1989.

Refereed journal papers

-        A. Cseh, R.W. Irving and D.F. Manlove, The stable roommates problem with short lists, Theory of Computing Systems vol. 63 (2019), pp. 128-149.

-        P. Biro, T, Fleiner and R.W. Irving, Matching couples with Scarf's Algorithm, Annals of Mathematics and Artificial Intelligence vol. 77 (2016), pp. 303-316.

-        E. McDermid and R.W. Irving, Sex-equal stable matchings:  complexity and exact algorithms, Algorithmica vol. 68 (2014), pp. 545-570.

-        T. Inoshita, R.W. Irving, K. Iwama, S. Miyazaki and T. Nagase, Improving man-optimal stable matchings by minimum change of preference lists, Algorithms 6 (2013), pp. 371-382.

-        T. Fleiner, R.W. Irving and D.F. Manlove, An algorithm for a super stable roommates problem, Theoretical Computer Science vol. 412 (2011), pp. 7059-7065.

-        P. Biro, R.W. Irving and I. Schlotter, Stable matching with couples: an empirical study, ACM Journal of Experimental Algorithmics, vol. 16 (2011), section 1 article no. 2, 27 pages.

-        E. McDermid and R.W. Irving, Popular matchings: structure and algorithms, Journal of Combinatorial Optimization vol. 22 (2011), pp. 339-358.

-        P. Biro, T, Fleiner, R.W. Irving and D.F. Manlove, The College Admissions problem with lower and common quotas, Theoretical Computer Science, vol. 411 (2010), pp. 3136-3153.

-        S. Fairley , J. D. McClure , N. Hanlon , R.W. Irving, M.W. McBride , A. F. Dominiczak and E. Hunt, Mapping Affymetrix microarray probes to the rat genome via a persistent index, International Journal of Knowledge Discovery in Bioinformatics vol. 1 (2010), pp. 48-65.

-        R.W. Irving and D.F. Manlove, Finding large stable matchings, ACM Journal of Experimental Algorithmics vol. 14 (2009), section 1 article no. 2, 30 pages.

-        R.W. Irving, D.F. Manlove and G. O'Malley, Stable marriage with ties and bounded length preference lists, Journal of Discrete Algorithms vol. 7 (2009), pp. 213-219.

-        R.W. Irving, Stable matching problems with exchange restrictions, Journal of Combinatorial Optimization vol. 16 (2008), pp. 344-360.

-        R.W. Irving, D.F. Manlove and S. Scott, The stable marriage problem with master preference lists, Discrete Applied Mathematics vol. 156 (2008), pp. 2959-2977.

-        R.W. Irving and D.F. Manlove, Approximation algorithms for hard variants of the stable marriage and hospitals / residents problems, Journal of Combinatorial Optimization vol. 16 (2008), pp. 279-292.

-        D.J. Abraham, R.W. Irving, K. Mehlhorn and K. Telikepalli, Popular matchings, SIAM Journal on Computing vol. 37 (2007), pp. 1030-1045.

-        R.W. Irving and S. Scott, The stable fixtures problem - a many-to-many extension of stable roommates, Discrete Applied Mathematics vol. 155 (2007), pp. 2118-2129.

-        T. Fleiner, R.W. Irving and D.F. Manlove, Efficient algorithms for generalised stable marriage and roommates problems, Theoretical Computer Science vol. 381 (2007), pp. 162-176.

-        R.W. Irving, The cycle roommates problem: a hard case of kidney exchange, Information Processing Letters vol. 103 (2007), pp. 1-4.

-        D.J. Abraham, R.W. Irving and D.F. Manlove, Two algorithms for the student-project allocation problem, Journal of Discrete Algorithms vol. 5 (2007), pp. 73-90. Postprint

-        R.W. Irving, D. Michail, K. Mehlhorn, K. Paluch and K. Telikepalli, Rank-maximal matchings, ACM Transactions on Algorithms vol. 2 (2006), pp. 602-610.

-        R.W. Irving and L. Love, The suffix binary search tree and suffix AVL tree, Journal of Discrete Algorithms vol. 1 (2003), pp. 387-408.

-        M. Halldorsson, R.W. Irving, K. Iwama, D.F. Manlove, S. Miyazaki, Y. Morita and S. Scott, Approximability results for stable marriage problems with ties, Theoretical Computer Science vol. 306 (2003), pp. 431-437.

-        E. Hunt, M.P. Atkinson and R.W. Irving, Database Indexing for large DNA and Protein Sequence Collections, VLDB Journal, vol. 11 (2002), pp. 256-271.

-        R.W. Irving and D.F. Manlove, The stable roommates problem with ties, Journal of Algorithms, vol. 43 (2002), pp. 85-105.

-        D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, and Y. Morita, Hard variants of stable marriage, Theoretical Computer Science,  vol. 276 (2002), pp. 261-279.

-        D.A. Christie and R.W. Irving, Sorting strings by reversals and by transpositions, SIAM Journal on Discrete Mathematics, vol. 14 (2001), pp. 193-206.

-        B.D. Flury, M.N. Goria and R.W. Irving, Magic dice, American Mathematical Monthly, vol. 106 (1999), pp. 324-337.

-        R.W. Irving and D.F. Manlove, The B-chromatic number of a graph, Discrete Applied Mathematics, vol. 91 (1999), pp. 127-141.

-        C. B. Fraser, R.W. Irving and M. Middendorf, Maximal common subsequences and minimal common supersequences, Information and Computation, vol. 124 (1996), pp. 145-153.

-        R. W. Irving and C. B. Fraser, Approximation algorithms for the shortest common supersequence, Nordic Journal of Computing, vol. 2 (1995), pp. 303-325.

-        B. G. Pittel and R. W. Irving, An upper bound for the solvability probability of a random stable roommates instance, Random Structures and Algorithms, vol. 5 (1994), pp. 465-486.

-        R. W. Irving and M. R. Jerrum, Three-dimensional statistical data security problems, SIAM Journal on Computing, vol. 23 (1994), pp. 170-184.

-        R. W. Irving, Stable marriage and indifference, Discrete Applied Mathematics, vol. 48 (1994), pp. 261-272.

-        R. W. Irving, On approximating the minimum independent dominating set, Information Processing Letters, vol. 37 (1991), pp. 197-200.

-        D. Gusfield and R.W. Irving, Parametric stable marriage and minimum cuts, Information Processing Letters, vol. 30 (1989), pp. 255-259.

-        D. Gusfield, R.W. Irving, P. Leather & M. Saks, Every finite distributive lattice is a set of stable matchings for a small stable marriage instance, J. Combinatorial Theory (A), vol. 44 (1987), pp. 304-309.

-        R.W. Irving, P. Leather & D. Gusfield, An efficient algorithm for the optimal stable marriage, Journal of the ACM, vol. 34 (1987), pp. 532-544.

-        R.W. Irving and P. Leather, The complexity of counting stable marriages, SIAM Journal on Computing, vol. 15 (1986), pp. 655-667.

-        R.W. Irving, An efficient algorithm for the stable roommates problem, Journal of Algorithms, vol. 6 (1985), pp. 577-595.

-        R.W. Irving, Permutation backtracking in lexicographic order, The Computer Journal, vol. 27 (1984), pp. 373-375.

-        R.W. Irving, NP-completeness of a family of graph-colouring problems, Discrete Applied Mathematics, vol. 5 (1983), pp. 111-117.

-        R. Hill and R.W. Irving, On group partitions associated with lower bounds for symmetric Ramsey numbers, European J. Combinatorics, vol. 3 (1982), pp. 35-50.

-        R.W. Irving, A bipartite Ramsey problem and the Zarankiewicz numbers, Glasgow Mathematical Journal, vol. 19 (1978), pp. 13-26.

-        R.W. Irving, Generalised Ramsey numbers for small graphs, Discrete Mathematics vol. 9 (1974), pp. 251-264.

-        R.W. Irving, An extension of Schur's theorem on sum-free partitions, Acta Arithmetica vol. 25 (1973), pp. 55-64.

-        R.W. Irving, On a bound of Graham and Spencer for a graph-colouring constant, J. Combinatorial Theory (B) vol. 15 (1973), pp. 200-203.

Conference papers

-      A. Cseh, R.W. Irving and D.F. Manlove, The stable roommates problem with short lists, Proceedings of SAGT 2016: the 9th International Symposium on Algorithmic Game Theory, Lecture Notes in Computer Science vol. 9928 (Springer 2016), pp. 207-219.

-        A. Kwanashie, D.F. Manlove, R.W. Irving and C. Sng, Profile-based optimal matchings in the Student-Project Allocation problem, Proceedings of IWOCA 2014: the 25th International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science vol. 8986 (Springer 2015), pp. 213-225.

-        B. Rastegari, A. Condon, N. Immorlica, R.W. Irving and K. Leyton-Brown, Reasoning about optimal stable matchings under partial information, Proceedings of 15th ACM Conference on Economics and Computation, Palo Alto, California, June 2014 (ACM 2014), pp. 431-448.

-        P. Biro, R.W. Irving and D.F. Manlove, Popular matchings in the Marriage and Roommates problems, Proceedings of CIAC 2010, the seventh International Conference on Algorithms and Complexity, Rome, May 2010, Lecture Notes in Computer Science vol. 6078 (Springer 2010), pp. 97-108.

-        E. McDermid and R.W. Irving, Popular matchings: structure and algorithms, Proceedings of COCOON 2009, 15th Annual International Computing and Combinatorics Conference, Niagara Falls USA, July 2009, Lecture Notes in Computer Science vol. 5609 (Springer 2009), pp. 506-515.

-        R.W. Irving and D.F. Manlove, An 8/5 approximation algorithm for a hard variant of stable marriage, in Proceedings of COCOON 2007, 13th Annual International Computing and Combinatorics Conference, Banff Canada, July 2007, Lecture Notes in Computer Science vol. 4598 (Springer 2007), pp. 548-558. 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, which is available as Technical Report no. TR-2007-258 of the Computing Science Department of Glasgow University, 2007.

-        D.J. Abraham, R.W. Irving, K. Mehlhorn and K. Telikepalli, Popular matchings, Proceedings of SODA 2005, 16th ACM/SIAM Symposium on Discrete Algorithms, Vancouver, January 2005, pp. 424-432.

-        R.W. Irving, D. Michail, K. Mehlhorn, K. Paluch and K. Telikepalli, Rank-maximal matchings, Proceedings of SODA 2004, 15th ACM/SIAM Symposium on Discrete Algorithms, New Orleans, January 2004, pp. 68-75.

-        D.J. Abraham, R.W. Irving and D.F. Manlove, The student-project allocation problem, Proceedings of ISAAC 2003, Kyoto Japan, December 2003, Lecture Notes in Computer Science vol. 2906 (Springer 2003), pp. 474-484.

-        R.W. Irving, D.F. Manlove and S. Scott, Strong stability in the hospitals/residents problem, Proceedings of STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin February/March 2003, Lecture Notes in Computer Science vol. 2607 (Springer 2003), pp. 439-450.

-        E. Hunt, M.P. Atkinson and R.W. Irving, A database index to large biological sequences, Proceedings of 27th Annual International Conference on Very Large Databases, Rome, September 2001, (Morgan-Kaufmann), pp. 139-148.

-        I.P. Gent, R.W. Irving, D.F. Manlove, P. Prosser and B.M. Smith, A constraint programming approach to stable marriage, Proceedings of CP2001, the 7th International Conference on the Principles and Practice of Constraint Programming, Paphos Cyprus, November 2001, Lecture Notes in Computer Science vol. 2239 (Springer 2001), pp. 225-239.

-        R.W. Irving, D.F. Manlove and S. Scott, The hospitals/residents problem with ties, Proceedings of SWAT 2000, the 7th Scandinavian Workshop on Algorithm Theory, Bergen Norway, July 2000, Lecture Notes in Computer Science vol. 1851 (Springer 2000), pp. 259-271.

-        R. W. Irving, Matching medical students to pairs of hospitals: a new variation on an old theme, in Proceedings of ESA'98, the Sixth Annual European Symposium on Algorithms, Venice Italy, 1998, Lecture Notes in Computer Science, vol. 1461 (Springer 1998), pp. 381-392.

-        R. W. Irving & C. B. Fraser, Maximal common subsequences and minimal common supersequences, in Proceedings of CPM'94, the Fifth Annual Symposium on Combinatorial Pattern Matching, Asilomar California, 1994, Lecture Notes in Computer Science, vol. 807 (Springer 1994), pp. 173-183.

-        R. W. Irving & C. B. Fraser, On the worst-case behaviour of some approximation algorithms for the shortest common supersequence, in Proceedings of CPM'93, the Fourth Annual Symposium on Combinatorial Pattern Matching, Padova Italy, 1993, Lecture Notes in Computer Science, vol. 684 (Springer 1993), pp. 63-73.

-        R. W. Irving & C. B. Fraser, Two algorithms for the longest common subsequence of three (or more) strings, in Proceedings of CPM'92, the Third Annual Symposium on Combinatorial Pattern Matching, Tucson Arizona, 1992, Lecture Notes in Computer Science, vol. 644 (Springer 1992), pp. 214-229.

Workshop papers

-      P. Biro, T. Fleiner and R.W. Irving, Matching couples with Scarf's algorithm, in Proceedings of the 8th Hungarian-Japanese Symposium on Discrete Mathematics and its Applications (HJ 2013) (Veszprem, Hungary).

-        T. Inoshita, R.W. Irving, K. Iwama, S. Miyazaki, and T. Nagase, Improving man-optimal stable matchings by minimum change of preference lists, in Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and its Applications (HJ 2011), pp. 309-313, 2011. (Kyoto, Japan).

-        T. Fleiner, R.W. Irving and D.F. Manlove, An algorithm for a super-stable roommates problem, in Proceedings of HJ07: the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2007.

-        R.W. Irving, D.F. Manlove and G. O'Malley, Stable marriage with ties and bounded length preference lists, in Proceedings of ACID 2006, volume 7 of Texts in Algorithmics, College Publications, 2006, pp. 95-106. Postprint

Other publications

-        K. Cechlarova, R.W. Irving and D.F. Manlove, Stability in labour market games, ERCIM News vol. 57 (2004), pp. 27-28.

-        R.W. Irving, Stable matching problems, Mathematical Spectrum, vol. 18 (1985), pp. 6-14.

-        R.W. Irving, Towards an optimum Mastermind strategy, J. Recreational Math., vol. 11 (1979), pp. 81-87.

Technical reports (not superseded by other publications).

-        P. Biro, R.W. Irving and I Schlotter, Stable matching with couples: theory and practice, University of Glasgow, School of Computing Science Research Report, TR-2011-324, February 2011.

-        R.W. Irving and D.F. Manlove, Finding large stable matchings, University of Glasgow, Computing Science Department Research Report, TR-2008-288, September 2008.

-        R.W. Irving, Man-Exchange Stable Marriage, University of Glasgow, Computing Science Department Research Report, TR-2004-177, August 2004.

-        R.W. Irving, Plagiarism and collusion detection using the Smith-Waterman Algorithm, University of Glasgow, Computing Science Department Research Report, TR-2004-164, April 2004.

-        R.W. Irving, Greedy matchings, University of Glasgow, Computing Science Department Research Report, TR-2003-136, April 2003.

-        R.W. Irving and L. Love, Suffix binary search trees and suffix arrays, University of Glasgow, Computing Science Department Research Report, TR-2001-82, March 2001.

-        E. Hunt, R.W. Irving and M.P. Atkinson, Persistent suffix trees and suffix binary search trees as DNA sequence indexes, University of Glasgow, Computing Science Department Research Report, TR-2000-63, October 2000.

-        R.W. Irving and D.F. Manlove, The stable roommates problem with ties, University of Glasgow, Computing Science Department Research Report, TR-2000-62, September 2000.

-        R.W. Irving and L. Love, The suffix binary search tree and suffix AVL tree, University of Glasgow, Computing Science Department Research Report, TR-2000-54, February 2000.

-        R.W. Irving and D.A. Christie, Sorting by reversals: on a conjecture of Kececioglu and Sankoff, University of Glasgow, Computing Science Department Research Report, TR-1995-12, May 1995.  

-        R.W. Irving, On the stable roommates problem, University of Glasgow, Computing Science Department Research Report, CSC-86-R5, July 1986



 

 


Rob Irving, rwi@dcs.glasgow.ac.uk