Enumerating k -Arc-Connected Orientations
- PDF / 341,052 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 208 Views
Enumerating k-Arc-Connected Orientations Sarah Blind1 · Kolja Knauer2,3 · Petru Valicov3,4 Received: 26 November 2019 / Accepted: 15 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study the problem of enumerating the k-arc-connected orientations of a graph G, i.e., generating each exactly once. A first algorithm using submodular flow optimization is easy to state, but intricate to implement. In a second approach we present a simple algorithm with O(knm 2 ) time delay and amortized time O(m 2 ), which improves over the analysis of the submodular flow algorithm. As ingredients, we obtain enumeration algorithms for the α-orientations of a graph G in O(m 2 ) time delay and for the outdegree sequences attained by k-arc-connected orientations of G in O(knm 2 ) time delay. Keywords Enumeration · Graph orientations · Connectivity
The first author was supported by the French ANR project GraphEn: ANR-15-CE40-0009. The second and third authors were supported by the French ANR project DISTANCIA: ANR-17-CE40-0015. The second author moreover was supported by ANR grant GATO: ANR-16-CE40-0009-01 and by the Spanish Ministerio de Economía, Industria y Competitividad through Grant RYC-2017-22701.
B
Petru Valicov [email protected] Sarah Blind [email protected] Kolja Knauer [email protected]
1
LGIPM, Université de Lorraine, 57000 Metz, France
2
Departament de Matemàtiques i Informàtica, Universitat de Barcelona (UB), Barcelona, Spain
3
LIS - Aix-Marseille Univ, CNRS, Universié de Toulon, Marseille, France
4
LIRMM - CNRS, Université de Montpellier, Montpellier, France
123
Algorithmica
1 Introduction In an enumeration problem one receives a typically small input and wants to output every element of a typically large resulting set exactly once.1 Since the runtime of an enumeration algorithm depends on the output, usually one measures how much it exceeds the size of the output in terms of the size of the input. More precisely, one wants to control the delay, i.e., the maximum time between two consecutive outputs (including the time before the first and after the last output) in terms of the input or at least the average over these, called the amortized time. Clearly, the delay is an upper bound for the amortized time. An instance that illustrates this challenge perfectly is given an undirected (not necessarily simple) graph G, enumerate all its orientations with a given property. Many types of orientations have been studied with respect to their enumeration complexity, see [7] for an overview. Here we give just some examples, before describing the set-up of this paper. The set of all orientations of G = (V , E) can be identified with the set of vectors {0, 1}m where m = |E|. Thus, enumerating all orientations of G using a Gray code can be done with constant delay, see [14]. It gets more interesting when enumerating acyclic orientations, i.e. those that have no directed cycles. In [40] an algorithm for enumerating all acyclic orientations with O(n 3 ) time del
Data Loading...
