On the stable bb-matching problem in multigraphs

This paper deals with the stable bb-matching problem in multigraphs, called the stable multiple activities problem, SMA for short. In an SMA instance a multigraph G=(V,E)G=(V,E), capacity b(v)b(v) and a linear order ≺v≺v on the set of edges incident to vv, for each vertex v∈Vv∈V are given. A stable bb-matching is sought, i.e. a set of edges M   such that each vertex vv is incident with at most b(v)b(v) edges and for each edge e∉Me∉M a vertex vv incident with ee and b(v)b(v) distinct edges f1,…,fb(v)f1,…,fb(v) incident to vv exist in M  , all of them ≺v≺v-smaller than ee.We show how to decrease the computational complexity of the SMA algorithm to run in O(|E|)O(|E|) time and derive some properties of stable bb-matchings.