UMONS Faculté des sciences Institut d'Informatique Romain Absil

Changer de langue: Fr|En # Summary

I'm a FRIA research fellow at the Computer Science Insitute of Science Faculty of the University of Mons (UMons). I'm currently making a Ph. D. thesis under Hadrien Mélot direction, at the Computer Algorithms Lab.

# Research

My research field is based on graph theory, more particularly the directed model. I'm currently working on the price of symmetrisation problem involving the average distance (cf. Phd thesis).

## Publications

Absil R and Mélot H., Digenes: genetic algorithms to discover conjectures about directed and undirected graphs. Discrete Applied Mathematics. Submitted on May 2013. arXiv:1304.7993.

Absil R and Mélot H., On price of symmetrisation. Discrete Applied Mathematics. Submitted on November 2013. arXiv:1310.2775.

## Main collaborations

• GERAD, HEC Montréal and Ecole Polytechnique de Montréal, more particularly Pierre Hansen, Gilles Caporossi and Alain Hertz team.

## Ph. D. thesis

There are nowadays many discovery systems assisting researchers on their works on undirected graphs. However, there exist no such system for directed graphs. This is mainly due to the fact that "undirected systems" use enumeration, which is unapplicable in the directed case (directed graphs are too numerous).

My thesis brings thus two types of contributions :

• Pratical : Develop and/or improve software to take charge of the directed case.
• Theorical : Use the developed systems directed extremal graph theory.

More particularly, I'm interested in the price of symmetrisation. Intuitively, given a graph invariant I, we search for the maximal difference between the value of I measured on a directed graph and its value valeur measured on the symmetric version of the graph (equivalent to the undirected model). We can provide a similar definition with a quotient operation.

# Teaching

I am currently assuming the following exercice sessions :

• Programmation and algorithmics 2,
• Approximation algorithms,
• Computer science project.

# Softwares

I collaborated with Gilles Caporossi during Autumn 2009 to create a prototype of AutoGraphiX (AGX) taking charge of directed graphs. However, this prototype have never been released.

I developped Digenes, an automated system helping discovery using a genetic algorithm metaheuristic. More particularly, Digenes deals with both directed and undirected graphs, and allows to :

• given a graph G, modify it with basic graph transformations, and follow associated invariants evolution,
• given an invariant I, launch a genetic algorithm in order to findgraphs maximising I,
• given a conjecture written as an equality or inequality between graph invariants, try to automatically find a counterexample to this conjecture,
• automatically find graphs satisfying a given set of constraints,
• validate a graph transformation (for instance, for all graphs, check wether a property always holds before and after a transformation.).