Article citationsMore>>

Khuller, S. and Raghavachari, B. (1996) Improved Approximation Algorithms for Uniform Connectivity Problems. Journal of Algorithms, 21, 434-450.
https://doi.org/10.1006/jagm.1996.0052

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.