Journées de l'optimisation 2018
HEC Montréal, Québec, Canada, 7 — 9 mai 2018
MB7 Graphs and networks
7 mai 2018 15h30 – 17h10
Salle: Groupe Cholette (35)
Présidée par Eglantine Camby
4 présentations

15h30  15h55
CANCELLED  Largescale graph clustering using metaheuristic techniques
We begin with the combinatorial optimizationbased graph clustering problems formulated by Fan and Pardalos and Aloise et al. After modifying the model formulations presented in the literature, we compare the performance of metaheuristic techniques, paying particular attention to scalability. We use simulated data sets as benchmarks.

15h55  16h20
Graph theory as a tool to analyze the writing process
Graph theory is useful to model a variety of situations from transportation (network flows) to biology, even when the data evolves with time. The process of writing a text is complicated to observe as the state of a text changes constantly. The goal of this research is to analyze the writing process, find insights on writing strategies and generate complex statistics using graph theory.

16h20  16h45
Optimizing a graph invariant based on a new distance
In this talk, we propose a new distance, defined as the expected length of a walk between any pair of vertices, and the RW Index, which sums the expected walks lengths between pairs of vertices. According to the computer system AutoGraphiX III, we conjecture on graphs minimizing/maximizing the RW Index.

16h45  17h10
Maximal number of leaves in induced subtrees
Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we require the subtrees to be induced and compute their maximal number of leaves. The problem, which is NPcomplete in general, becomes polynomial in the case of trees. The leaf function associates to a number n the maximal number of leaves an induced subtree of size n can have. To compute the leaf function, we provide an efficient branch and bound algorithm. In the particular case of trees, we describe a polynomial algorithm using the dynamic programming paradigm. We conclude by exhibiting a link between the leaf functions of caterpillar graphs and a particular class of words called prefix normal.