Videos

Arc connectivity and submodular flows in digraphs

Presenter
March 28, 2023
Abstract
Given a digraph D, and an integer k>=1, a k-arc-connected flip is an arc subset whose reversal makes the digraph (strongly) k-arc-connected. The main result of this work introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function. The main result has several applications to graph orientations and combinatorial optimization. For instance, if the underlying graph of D is t-edge-connected for some integer t>=2, there exists a decomposition of the arc set into a k-arc-connected flip and a (t-k)-dijoin, for any integer k such that 1
Supplementary Materials