Name
Abstract | ||
|---|---|---|
As a generalisation of the stable matching problem Baiou and Balinski (2002) [1] 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.disopt.2010.02.002 | Discrete Optimization |
Keywords | Field | DocType |
scaling technique,stable matching problem,so-called inductive algorithm,roommates problem,non-bipartite graph,bipartite graph,stable allocation,stable allocation problem,polynomial time,integral capacity,integral stable allocation problem,algorithm weakly polynomial,stable matching | Stable roommates problem,Discrete mathematics,Mathematical optimization,Combinatorics,Stable marriage problem,Vertex (geometry),Polynomial,Bipartite graph,Matching (graph theory),Hopcroft–Karp algorithm,3-dimensional matching,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 1-2 | Discrete Optimization |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Péter Biró | 1 | 237 | 19.83 |
| Tamás Fleiner | 2 | 241 | 27.45 |