Skip to Main content Skip to Navigation
Theses

Output-sensitive algorithms for enumeration problems in graphs

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²).
Complete list of metadata

Cited literature [114 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-02875095
Contributor : Thèses Ul Connect in order to contact the contributor
Submitted on : Friday, June 19, 2020 - 1:58:25 PM
Last modification on : Saturday, June 20, 2020 - 3:16:47 AM

Identifiers

  • HAL Id : tel-02875095, version 1

Citation

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

Share

Metrics

Record views

114

Files downloads

227