4 Presentations

• 
  03:30 PM - 03:55 PM

  CANCELLED - Large-scale graph clustering using metaheuristic techniques

  • Pierre Miasnikof, presenter, University of Toronto
  • Anthony J. Bonner, Dept. of Computer Science, University of Toronto
  • Yuri Lawryshyn, Dept. of Chemical Engineering and Applied Chemistry, University of Toronto

  We begin with the combinatorial optimization-based 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

  • Helene-Sarah Becotte-Boutin, presenter, Polytechnique
  • Gilles Caporossi, GERAD, HEC Montréal
  • Alain Hertz, GERAD, Polytechnique Montréal

  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

  • Eglantine Camby, presenter, Université Libre de Bruxelles
  • Gilles Caporossi, GERAD, HEC Montréal
  • Marcia Paiva, Federal University of Espirito Santo
  • Marcelo Segatto, Federal University of Espirito Santo

  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

  • Élise Vandomme, presenter, Université du Québec à Montréal
  • Alexandre Blondin Massé, Université du Québec à Montréal
  • Julien de Carufel, Université du Québec à Trois Rivières
  • Alain Goupil, Université du Québec à Trois Rivières
  • Mélodie Lapointe, Université du Québec à Montréal
  • Émile Nadeau, Université du Québec à Montréal

  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 NP-complete 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.