Abstract Popular Matchings (2008)
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly involving...
Stable marriage with ties and bounded length preference lists (2008)
Robert W. Irving, David F. Manlove
Abstract. We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical...
Efficient algorithms for generalised stable marriage and (2008)
Tamás Fleiner, Robert W. Irving, David F. Manlove
roommates problems
Ela Hunt, Malcolm P. Atkinson, Robert W. Irving
Abstract. Our aim is to develop new database technologies for the approximate matching of unstructured string data using indexes. We explore the potential of the suffix tree data structure in this...
Ela Hunt, Malcolm P. Atkinson, Robert W. Irving
Abstract. Our aim is to develop new database technologies for the approximate matching of unstructured string data using indexes. We explore the potential of the suffix tree data structure in this...
Robert W. Irving, David F. Manlove, Robert W. Irving, David F. Manlove
Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems ∗,†
Irving, Robert W., Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
Suppose that each member of a set of n applicants ranks a subset of a set of m posts in strict order of preference. A matching is a set of (post, applicant) pairs such that each applicant and each...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly...
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set�of applicants ranks a subset of a set Èof posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
David J. Abraham, Robert W. Irving, David F. Manlove
Abstract. We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals / Residents problem (HR). An instance of SPA involves a set of students, projects and...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of matching a set of applicants to a set of posts, where each applicant ranks a non-empty subset of posts in an order of preference, possibly involving ties. We say that a...
Strong stability in the hospitals/residents problem (2003)
Robert W. Irving, Robert W. Irving, David F. Manlove, David F. Manlove, Y Scott, Y Scott
We study a version of the well-known Hospitals/Residents problem in which participants ’ preferences may involve ties or other forms of indifference. In this context, we investigate the concept of...
Approximability results for stable marriage problems with ties. Theoretical Computer Science (2003)
Magnús M. Halldórsson, Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita
We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the...
Approximability results for stable marriage problems with ties. Theoretical Computer Science (2003)
Magnús M. Halldórsson, Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita
We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the...
The stable roommates problem with ties (2002)
Robert W. Irving, David F. Manlove
We study the variant of the well-known Stable Roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability...
variants of stable marriage (2002)
David F. Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita
The Stable Marriage Problem and its many variants have been widely studied in the literature [6, 22, 15], partly because of the inherent appeal of the problem, partly because of the elegance of the...
A constraint programming approach to the stable marriage problem (2001)
Ian P. Gent, Robert W. Irving, David F. Manlove, Patrick Prosser
b. m. smthhud. ac. uk Abstract. The Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an...
Suffix Binary Search Trees and Suffix Arrays (2001)
Suffix arrays and suffix binary search trees are two data structures that have been proposed as alternatives to the classical suffix tree to facilitate efficient on-line string searching. Here, we...
A Database Index to Large Biological Sequences (2001)
Ela Hunt, Malcolm P. Atkinson, Robert W. Irving
We present an approach to searching genetic DNA sequences using an adaptation of the sufx tree data structure deployed on the general purpose persistent Java platform, PJama. Our implementation...
A Constraint Programming Approach to the (2001)
Stable Marriage Problem, Ian P. Gent, Robert W. Irving, David F. Manlove, Patrick Prosser, Barbara M. Smith
The Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a...
A Database Index to Large Biological Sequences (2001)
Ela Hunt, Malcolm P. Atkinson, Robert W. Irving
We present an approach to searching genetic DNA sequences using an adaptation of the sufx tree data structure deployed on the general purpose persistent Java platform, PJama. Our implementation...
The suffix binary search tree and suffix AVL tree (2000)
Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string...
Persistent suffix trees and suffix binary search trees as DNA sequence indexes (2000)
Ela Hunt, Robert W. Irving, Malcolm Atkinson
We constructed, stored on disk and reused suffix trees and suffix binary search trees for C. elegans chromosomes, and measured their performance using orthogonal persistence for Java (PJama). We...
The suffix binary search tree and suffix AVL tree (2000)
Abstract Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string...
The b-chromatic number of a graph (1999)
Robert W. Irving, David F. Manlove
The achromatic number ψ(G) of a graph G = (V, E) is the maximum k such that V has a partition V1, V2,..., Vk into independent sets, the union of no pair of which is independent. Here we show that...
Maximal Common Subsequences and Minimal Common Supersequences (1995)
Campbell B. Fraser, Robert W. Irving, Martin Middendorf
The problems of finding a longest common subsequence and a shortest common supersequence of a set of strings are well-known. They can be solved in polynomial time for two strings (in fact the...
The Stable Marriage Problem (1989)
Abstract. We study a variant of the classical stable marriage problem in which there is an additional requirement for a stable matching, namely that there should not be two men each of whom prefers...