Аннотация:
В работе рассматривается модель стабильных реберных подмножеств (“матчингов”) в двудольном графе $G = (V, E)$, в котором предпочтения для вершин одной доли (“фирм”) задаются при помощи функций выбора со стандартными свойствами консистентности, заменяемости и кардинальной монотонности, а предпочтения для вершин другой доли (“работников”) – при помощи линейных порядков. Для такой модели дается комбинаторное описание структуры ротаций и предлагается алгоритм построения посета ротаций с оценкой временно́й сложности $O(|E|^2)$ (включая обращения к оракулам, связанных с функциями выбора). Как следствие, можно получить “компактное” аффинное представление стабильных матчингов и эффективно решать смежные задачи.
Библ. 21.
Список цитирования