Affordable Access

The integral stable allocation problem on graphs

Publication Date
  • Computer Science


As a generalisation of the stable matching problem Baton and Balinski (2002) 111 defined the stable allocation problem for bipartite graphs, where both the edges and the vertices may have capacities. They constructed a so-called inductive algorithm, that always finds a stable allocation in strongly polynomial time. Here, we generalise their algorithm for non-bipartite graphs with integral capacities. We show that the algorithm does not remain polynomial, although we also present a scaling technique that makes the algorithm weakly polynomial.

There are no comments yet on this publication. Be the first to share your thoughts.