The integral stable allocation problem on graphs

DOI10.1016/j.disopt.2010.02.002zbMath1264.05098OpenAlexW2045868247MaRDI QIDQ1952506

Tamás Fleiner, Péter Biró

Publication date: 31 May 2013

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.02.002

zbMATH Keywords

strongly polynomial timestable matching problemroommates problemstable allocation problemedge capacityinductive algorithmintegral capacitiesvertex capacityweakly polynomial algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Traffic problems in operations research (90B20) Boolean programming (90C09) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Faster algorithms for stable allocation problems ⋮ Fractional solutions for capacitated NTU-games, with applications to stable matchings

Cites Work

• Unnamed Item
• Unnamed Item
• On a lemma of Scarf.
• Stable schedule matching under revealed preference.
• On the stable \(b\)-matching polytope.
• A generalization of the stable matching problem
• The stable crews problem
• The stable fixtures problem -- a many-to-many extension of stable roommates
• The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems
• On a generalization of the stable roommates problem
• A necessary and sufficient condition for the existence of a complete stable matching
• Random Paths to Stability in Two-Sided Matching
• An upper bound for the solvability probability of a random stable roommates instance
• Algorithms and Computation
• The Stable Allocation (or Ordinal Transportation) Problem
• College Admissions and the Stability of Marriage

This page was built for publication: The integral stable allocation problem on graphs