<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>9324</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Fleiner,T.</AUTHOR></AUTHORS><YEAR>2010</YEAR><TITLE>Integral Stable Allocation Problem on Graphs</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2010-312</ISBN><LABEL>Biro:2010:9324</LABEL><KEYWORDS><KEYWORD>stable matching problem</KEYWORD></KEYWORDS<ABSTRACT>As a generalisation of the stable matching problem Baiou and Balinski 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.</ABSTRACT></RECORD></RECORDS></XML>