Ph.D

Group : Graphs, ALgorithms and Combinatorics

*Combinatorial Algorithms and Optimization*
Starts on 01/12/2014

Advisor : DEZA, Antoine

[COHEN Johanne]

**Funding :** Bourse association

**Affiliation :** Université Paris-Sud

**Laboratory :** LRI - GALaC

**Defended** on 15/11/2017, committee :

Co-directrice de thèse :

- Johanne Cohen, Paris-Sud;

Co-directeur de thèse

- Antoine Deza,Paris-Sud.

Raporteurs :

- Ralf Klasing, Bordeaux;

- Dmitri Pasechnik, Oxford;

- Lionel Pournin, Paris XIII.

Examinateurs :

- Ioan Todinca, Orléans;

- Michele Sebag, Paris-Sud;

- Cristina Bazgan, Université Paris-Dauphine.

**Research activities :**
**Abstract :**
We investigate three main questions in this thesis. The rst two are related to

graph algorithmic problems. Given general or restricted classes of graphs, we design

algorithms in order to achieve some given result.

We start by introducing the class of k-degenerate graphs which are often used to

model sparse real world graphs. We then focus on enumeration questions for these

graphs. That is, we try and provide algorithms which must output, without duplication,

all the occurrences of some input subgraph with some given properties. In

the scope of this thesis, we investigate the questions of nding all subgraphs which

have the property to be cycles of some given size and all subgraphs which have the

property to be maximal cliques in the input sparse graph. Our two main contributions

related to these problems are a worst-case output size optimal algorithm for

xed-size cycle enumeration and an output sensitive algorithm for maximal clique

enumeration for this restricted class of graphs.

The second main object that we study is also related to graph algorithmic questions,

although in a very dierent setup. We want to consider graphs in a distributed

manner. Each vertex or node has some computing power and can communicate with

its neighbors. Nodes must then cooperate in order to solve a global problem. In

this context, we mainly investigate questions related to nding matchings (a set of

edges of the graph with no common end vertices) assuming any possible initialization

(correct or incorrect) of the system. These algorithms are often referred to as

self-stabilizing since no assumption is made on the initial state of the system. In

this context, our two main contributions are the rst polynomial time self-stabilizing

algorithm returning a 2=3-approximation of the maximum matching and a new selfstabilizing

algorithm for maximal matching when communication is restricted in

such a way as to simulate the message passing paradigm.

Our third object of study is not related to graph algorithms, although some

classical techniques are borrowed from that eld to achieve some of our results.

We introduce and investigate some special families of polytopes, namely primitive

zonotopes, which can be described as the Minkowski sum of short primitive vectors.

We prove some of their combinatorial properties and highlight connections with the

largest possible diameter of the convex hull of a set of points in dimension d whose

coordinates are integers between 0 and k. Our main contributions are new lower

bounds for this diameter question as well as descriptions of small instances of these

polytopes.