The Strongly Stable Roommates Problem
| Autor: | Kunysz, Adam |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
000 Computer science
knowledge general works 010201 computation theory & mathematics Computer Science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology 01 natural sciences MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.4230/lipics.esa.2016.60 |
| Popis: | An instance of the strongly stable roommates problem with incomplete lists and ties (SRTI) is an undirected non-bipartite graph G = (V,E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertex-disjoint edges. An edge {x, y} in E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present an O(nm) time algorithm for computing a strongly stable matching, where we denote n = |V| and m = |E|. The best previously known solution had running time O(m^2) [Scott, 2005]. We also give a characterisation of the set of all strongly stable matchings. We show that there exists a partial order with O(m) elements representing the set of all strongly stable matchings, and we give an O(nm) algorithm for constructing such a representation. Our algorithms are based on a simple reduction to the bipartite version of the problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|