HEC Montréal, Canada, 2 - 4 mai 2011

Journées de l'optimisation 2011

HEC Montréal, Canada, 2 — 4 mai 2011

Horaire Auteurs Mon horaire

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

3 présentations

  • 10h30 - 10h55

    On the Extremal Values of the Second Largest Signless Laplacian Eigenvalue

    • Claire Lucas, prés., 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.

  • 10h55 - 11h20

    Line Graph Transformation to the Euler Tour with Movement Prohibition Problem

    • Marcos José Negreiros, prés., 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.

  • 11h20 - 11h45

    The Process of Writing Represented as a Graph

    • Christophe Leblay, University of Jyvaskyla
    • Gilles Caporossi, prés., 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.