21-25 August 2012
Portorož, Slovenia
UTC timezone
Home > Timetable > Contribution details

Digenes, a new tool using genetic algorithms for directed extremal graph theory

Presented by Mr. Romain ABSIL
Type: Oral presentation


There are nowadays many automated systems [3] helping researchers in graph theory, such as Graffiti (1987) [2], AutoGraphiX (AGX) (2000) [1] and Graphedron (2008) [4]. However, no system has been developed for directed graphs. Moreover, as most of existing systems use exact (and costly in time) algorithms, new approaches are needed. We introduce here <i>Digenes</i>, a new tool for directed extremal graph theory using genetic algorithms. This system has three main features. Firstly, given a class of graphs and a graph invariant, it allows to automatically find supposed extremal graphs for this invariant, using genetic algorithms. Moreover, given a graph transformation and a property, the system is able to heuristically check whether the property is hold before and after the transformation. Finally, Digenes is able to track invariant evolution under graph transformation. <p> <b>References</b> [1] CAPOROSSI , G., and HANSEN , P. Variable Neighborhood Search for Extremal Graphs 1. The AutoGraphiX System. Discrete Math. 212 (2000), 29–44. [2] FAJTLOWICZ , S. Written on the Wall. A regulary updated file accessible from <code>http://www.math.uh.edu/ ̃clarson/</code> [3] HANSEN , P., and MÉLOT, H. Computers and Discovery in Algebraic Graph Theory. Linear Algebra and its Applications 356 (2002), 211 – 230. [4] MÉLOT, H. Facet defining inequalities among graph invariants : the system GraPHedron. Discrete Appl. Math. 156 (2008), 1875–1891


Location: Portorož, Slovenia
Address: University of Primorska, Faculty of Tourism Studies, Obala 11a, SI-6320 Portorož - Portorose, Slovenia
Room: VP1

Primary authors