2024/09/23 by П. А. Архипов, Vladimir Kolmogorov, Arkhipov, Pavel +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2409.14881
openalex publication_date 2024/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider two problems for a directed graph G, which we show to be closely related. The first one is to find k edge-disjoint forests in G of maximal size such that the indegree of each vertex in these forests is at most k. We describe a min-max characterization for this problem and show that it can be solved in O(k δm log n) time, where (n,m) is the size of G and δ is the difference between k and the edge connectivity of the graph. The second problem is the directed edge-connectivity augmentation problem, which has been extensively studied before: find a smallest set of directed edges whose addition to the graph makes it strongly k-connected. We improve the complexity for this problem from O(k δ(m+δn)log n) [Gabow, STOC 1994] to O(k δm log n), by exploiting our solution for the first problem. A similar approach with the same complexity also works for the undirected version of the problem.