Article citationsMore>>

Frank, A. and Tardos, É. (1989) An Application of Submodular Flows. Linear Algebra and its Applications, 114, 329-348.
https://doi.org/10.1016/0024-3795(89)90469-2

has been cited by the following article:

• TITLE: On Packing Edge-Disjoint Cycles in Digraphs and Its Applications in Connectivity Problems

  AUTHORS: Vardges Melkonian

  KEYWORDS: Directed Graphs, Cycle Packing, Node Connectivity, Approximation Algorithms

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.16 No.4, September 23, 2026

  ABSTRACT: We consider the problem of packing edge-disjoint cycles in digraphs. It is shown that for k=2,3 , any digraph with minimum degree k contains at least k+1 edge-disjoint directed cycles of size ≥k . In each of these two cases, examples are given to show that k+1 edge-disjoint directed cycles is the best we can achieve. These results are applied to obtain approximation algorithms for k -node-connectivity problems.