On stable flows and preflows

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 p...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-10
Main Author: Karzanov, Alexander
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph theory
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.)
ISSN:2331-8422
DOI:10.48550/arxiv.2209.00614