3 Presentations

• 
  10:30 AM - 10:55 AM

  On the Extremal Values of the Second Largest Signless Laplacian Eigenvalue

  • Claire Lucas, presenter, GERAD, HEC Montréal
  • Moustapha Aouchiche, HEC Montréal
  • Pierre Hansen, HEC Montréal

  We study extremal graphs for the extremal values of the second largest signless Laplacian eigenvalue of a connected graph. We first characterize all simple connected graphs with second largest signless Laplacian eigenvalue at most 3.
  The second part of the present work is devoted to the study of the graphs that maximize the second largest signless Laplacian eigenvalue. We construct families of such graphs and prove that some of theses families are minimal for the fact that they maximize the second largest signless Laplacian eigenvalue.

• 
  10:55 AM - 11:20 AM

  Line Graph Transformation to the Euler Tour with Movement Prohibition Problem

  • Marcos José Negreiros, presenter, State University of Ceará
  • Augusto Palhano, GRAPHVS Cons., Com., Rep. Ltda

  We consider the problem of designing Euler Tours with movement prohibition by using Line Graph Transformations. Differently to the main approaches studied by the literature previously, the procedure can achieve nice results reducing drastically the number of short circles formed to be further combined. We define a number of different patching methods that perform circle combinations automatically and compare them with an exact B&B approach and the results obtained by the state of the art heuristic for the ATSP. All the tests were done for a number of real life garbage collection networks.

• 
  11:20 AM - 11:45 AM

  The Process of Writing Represented as a Graph

  • Christophe Leblay, University of Jyvaskyla
  • Gilles Caporossi, presenter, GERAD, HEC Montréal

  Computer keystroke logging tools enable to capture writing data. Our approach consists in merging the events in sequences and the links between them. The process of writing can be represented as a graph : each node represents a sequence of events whereas each edge identifies spatial or temporal relations between sequences.