| |
|
|
Abstract: This paper deals with the generalization of the classical stable roommates problem, called the Stable Multiple Activities problem, SMA for short. In an SMA instance a multigraph $G=(V,E)$, capacities $b(v)$ and a linear order $\prec_v$ on the set of edges incident to a vertex $v$ for each $v \in V$ are given. A stable \bb-matching is sought, i.e. a set of edges $M$ such that each vertex $v$ is incident with at most $b(v)$ edges and for each edge $e \notin M$ a vertex $v$ incident with $e$ and $b(v)$ different edges $f_1,\dots,f_{b(v)}$ incident to $v$ exist, all of them $\prec_v$-smaller than $e$. We show how to decrease the computational complexity of the SMA algorithm to run in $O(|E|)$ time and derive some properties of stable \bb-matchings. Contact the authors: cechlarova@science.upjs.sk, valova@science.upjs.sk Download PDF version of the preprint. |