Output-sensitive algorithms for enumeration problems in graphs - Université de Lorraine Access content directly
Theses Year : 2019

Output-sensitive algorithms for enumeration problems in graphs

Algorithmes "output-sensitifs" pour les problèmes d’énumération dans les graphes

Abstract

This thesis is a study, from an algorithmic point of view, of the complexity of solving some enumeration problems in graphs. Algorithms for enumeration problems are meant to produce all solutions of a combinatorial problem, without repetition. Because there is a potentially exponential number of solutions to be generated, different approaches to analyse the performance of those algorithms have been developed: the input-sensitive approach and the output-sensitive approach. The first is a measure of the complexity that is based on the size of the input, and which consists in analysing the total time needed to enumerate the objects. The second is a measure based on the size of the input and the output. Here we will be interested in an output-sensitive approach and we will pay special attention to the notion of delay, i.e., the time needed between the production of two consecutive solutions. The thesis is divided into two independent parts. In the first one we propose a general framework that allows for the study of enumeration of vertex set properties in graphs. We prove that when such a property is locally definable with respect to some order on the set of vertices, then it can be enumerated with linear delay. Our method is a reduction of the considered enumeration problem to the enumeration of paths in directed acyclic graphs. We apply this general method to enumerate with linear delay minimal connected dominating sets and maximal irredundant sets in interval graphs and in permutation graphs, as well as maximal irredundant sets in circular-arc graphs and in circular-permutation graphs. The second part of the thesis is dedicated to the study of k-arc-connected orientations. These are orientations for which at least k arcs have to be removed in order to destroy the strong connectivity. We first give a simple algorithm to enumerate the k-arc-connected orientations respecting some fix outdegree sequence. We then give a simple algorithm to enumerate the outdegree sequences attained by k-arc-connected orientations. Combining both yields an algorithm that enumerates all k-arc-connected orientations of a graph in delay O(knm²) and amortized time O(m²).
Cette thèse est une étude, d’un point de vue algorithmique, de la complexité de la résolution de certains problèmes d’énumération dans les graphes. Les algorithmes pour les problèmes d’énumération ont pour but la production de toutes les solutions d’un problème combinatoire, et ce sans répétition. Comme il existe un nombre potentiellement exponentiel de solutions à générer, différentes approches pour analyser la performance de ces algorithmes ont été développées: l’approche "input-sensitive" et l’approche "output-sensitive". La première est une mesure de la complexité basée sur la taille de l’entrée, elle consiste en l’analyse du temps total nécessaire à l’énumération des objets. La seconde est une mesure basée sur la taille de l’entrée et de la sortie. Nous nous intéresserons ici à l’approche output-sensitive et nous accorderons une attention particulière à la notion de délai, i.e., le temps nécessaire entre la production de deux solutions consécutives. La thèse est divisée en deux parties indépendantes. Dans la première, nous proposons un cadre général qui permet d’étudier l’énumération d’ensembles de sommets d’un graphe respectant une certaine propriété. Nous prouvons que lorsqu’une telle propriété peut être définie localement par rapport à un certain ordre sur l’ensemble des sommets du graphe, alors les ensembles de sommets respectant cette propriété peuvent être énumérés avec un délai linéaire. Notre méthode consiste à réduire le problème d’énumération considéré à l’énumération de chemins dans les graphes acycliques dirigés. Nous appliquons cette méthode générale pour énumérer avec un délai linéaire les ensembles dominants connexes minimaux et les ensembles irredondants maximaux dans les graphes d’intervalles et dans les graphes de permutation, ainsi que les ensembles irredondants maximaux dans les graphes arc-circulaires et dans les graphes permutation-circulaires. La deuxième partie de la thèse est consacrée à l’étude des orientations k-arc-connexes. Il s’agit d’orientations pour lesquelles il est nécessaire de supprimer au moins k arcs pour détruire la forte connexité. Nous présentons d’abord un algorithme simple pour énumérer les orientations k-arc-connexes respectant une séquence de degrés sortants. Ensuite nous présentons un algorithme simple pour énumérer les séquences de degrés sortants pour lesquelles il existe une orientation k-arc-connexe. En combinant ces deux algorithmes, nous obtenons un algorithme qui énumère toutes les orientations k-arc-connexes d’un graphe avec un délai de O(knm²) et un temps amorti de O(m²).
Fichier principal
Vignette du fichier
DDOC_T_2019_0323_BLIND.pdf (3.58 Mo) Télécharger le fichier
DDOC_T_2019_0323_BLIND_RESUME.pdf (483.98 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

tel-02875095 , version 1 (19-06-2020)

Identifiers

  • HAL Id : tel-02875095 , version 1

Cite

Sarah Blind. Output-sensitive algorithms for enumeration problems in graphs. Computer Science [cs]. Université de Lorraine, 2019. English. ⟨NNT : 2019LORR0323⟩. ⟨tel-02875095⟩
138 View
215 Download

Share

Gmail Facebook X LinkedIn More