On stable flows and preflows

DOI10.1134/S0965542523030077MaRDI QIDQ6039791zbMATH OpenOpenAlexFDO

Authors Alexander V. Karzanov

Publication date 23 May 2023

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.00614

zbMATH Keywords

preflowquasi-flowstable allocationstable flow in network

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Abstract: In 2010s Fleiner introduced a notion of stable flows in directed networks and showed that such a flow always exists and can be found by use of a reduction to the stable allocation problem due to Baiou and Balinski. Recently Cseh and Matuschke devised a direct strongly polynomial algorithm. In this paper we give an alternative algorithm to find a stable flow in a network with several sources and sinks. It is based on an idea of preflows (appeared in 1970s in a faster algorithm for the classical max-flow problem), and runs in $O(nm)$ time for a network with $n$ vertices and $m$ edges. The results are further generalized to a larger class of objects, so-called stable quasi-flows with bounded excesses in non-terminal vertices. (The paper is written in Russian.)

Cites work

• A data structure for dynamic trees
• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• College Admissions and the Stability of Marriage
• Erratum: The Stable Allocation (or Ordinal Transportation) Problem
• Faster algorithms for stable allocation problems
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• On stable matchings and flows
• Self-adjusting binary search trees
• Stable flows over time

Cited in

(1)

• Perturbing a product of stable flows

This page was built for publication: On stable flows and preflows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039791)