Enumerating k-arc-connected orientations
share
We give simple algorithms to enumerate the α-orientations of a graph G in delay O(m^2) and to enumerate the outdegree sequences attained by k-arc-connected orientations of G in delay O(knm^2). Combining both yields an algorithm that enumerates all k-arc-connected orientations of G in delay O(knm^2) and amortized time O(m^2). The latter improves over another approach using submodular flows and moreover is much simpler, since it is basically a combination of BFS searches.
READ FULL TEXT
