### Skapa referens, olika format (klipp och klistra)

**Harvard**

Cseh, Á., Huang, C. och Kavitha, T. (2015) *Popular matchings with two-sided preferences and one-sided ties*.

** BibTeX **

@conference{

Cseh2015,

author={Cseh, Á. and Huang, Chien-Chung and Kavitha, T.},

title={Popular matchings with two-sided preferences and one-sided ties},

booktitle={42nd International Colloquium on Automata, Languages and Programming, ICALP 2015; Kyoto; Japan; Lecture Notes in Computer Science },

isbn={978-3-662-47672-7},

pages={367-379},

abstract={We are given a bipartite graph G = (A ∪ B, E) where each vertex has a preference list ranking its neighbors: in particular, every a ∈ A ranks its neighbors in a strict order of preference, whereas the preference lists of b ∈ B may contain ties. A matching M is popular if there is no matching M’ such that the number of vertices that prefer M’ to M exceeds the number that prefer M to M’. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b ∈ B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b ∈ B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b’s list and and b desires to be matched to any of them. Our main result is an O(n2) algorithm (where n = |A ∪ B|) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not.},

year={2015},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 229765

A1 Cseh, Á.

A1 Huang, Chien-Chung

A1 Kavitha, T.

T1 Popular matchings with two-sided preferences and one-sided ties

YR 2015

T2 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015; Kyoto; Japan; Lecture Notes in Computer Science

SN 978-3-662-47672-7

SP 367

OP 379

AB We are given a bipartite graph G = (A ∪ B, E) where each vertex has a preference list ranking its neighbors: in particular, every a ∈ A ranks its neighbors in a strict order of preference, whereas the preference lists of b ∈ B may contain ties. A matching M is popular if there is no matching M’ such that the number of vertices that prefer M’ to M exceeds the number that prefer M to M’. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b ∈ B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b ∈ B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b’s list and and b desires to be matched to any of them. Our main result is an O(n2) algorithm (where n = |A ∪ B|) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not.

LA eng

DO 10.1007/978-3-662-47672-7_30

LK http://dx.doi.org/10.1007/978-3-662-47672-7_30

OL 30