HEC Montréal, Canada, 2 - 4 mai 2011
Journées de l'optimisation 2011
HEC Montréal, Canada, 2 — 4 mai 2011
TA5 Applications de la théorie des graphes / Applications of Graph Theory
3 mai 2011 10h30 – 12h10
Salle: Demers Beaulne
Présidée par Gilles Caporossi
10h30 - 10h55
On the Extremal Values of the Second Largest Signless Laplacian Eigenvalue
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.
10h55 - 11h20
Line Graph Transformation to the Euler Tour with Movement Prohibition Problem
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.
11h20 - 11h45
The Process of Writing Represented as a Graph
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.