Kolja Knauer: Generating k-connected orientations

Datum objave: 19. 5. 2019
Seminar za diskretno matematiko
Torek, 21. 5. 2019, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. We present a simple algorithm, that given a graph G generates all of its k-arc-connected orientations. Its amortized runtime is basically the same as the one of an algorithm that can be extracted from the theory of submodular flows. The latter is however rather intricate.

Another nice thing is, that our algorithm actually consists of two modules of independent interest:
1. an algorithm that generates all alpha-orientations of G for a given alpha,
2. an algorithm that generates all outdegree of k-connected orientations of G.

Joint with S. Blind and P. Valicov