2018 Optimization Days
HEC Montréal, Québec, Canada, May 7 — 9, 2018
MB7 Graphs and networks
May 7, 2018 03:30 PM – 05:10 PM
Location: Groupe Cholette (35)
Chaired by Eglantine Camby
4 Presentations

03:30 PM  03:55 PM
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.

03:55 PM  04:20 PM
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.

04:20 PM  04:45 PM
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.

04:45 PM  05:10 PM
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.