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

WA5 Théorie des graphes / Graph Theory

4 mai 2011 10h30 – 12h10

Salle: Demers Beaulne

Présidée par Odile Marcotte

4 présentations

  • 10h30 - 10h55

    Simultaneous Clustering

    • Zhentao Li, prés., McGill University

    We look for induced subgraphs which are simultaneously "nice" in a set of graphs. These graphs are defined over the same set of vertices, but with different sets of edges among them. This paradigm is very relevant in the biological sciences. We give inapproximability results for different definitions of "nice", such as high density or connectivity.

  • 10h55 - 11h20

    Disjoint Paths in Acyclic Planar Graphs

    • Guyslain Naves, prés., McGill University

    We consider the problem of finding arc-disjoint paths in a planar acyclic digraph, when the Euler condition is satisfied. We explain why this problem is hard to solve in general, and how to solve it when the number of commodities is fixed.

    (joint work with Christophe Weibel, Dartmouth University)

  • 11h20 - 11h45

    Fractional Total Colouring Graphs of Large Maximum Degree

    • Sean Kennedy, prés., McGill University

    The complexity of determining the fractional total colouring number is unresolved. Kilakos and Reed showed that it is always between D + 1 and D + 2, where D is the maximum degree. We discuss determining the fractional total colouring number for graphs of large maximum degree.

  • 11h45 - 12h10

    Model Order Reductions Through Vertex Cuts

    • Odile Marcotte, prés., Université du Québec à Montréal

    In order to test circuits, it is often necessary to replace the graph representing the circuit by a smaller graph having the same physical properties. This process, called model order reduction, keeps the so-called external nodes of the circuit but may greatly reduce the number of internal nodes. We give a precise definition of this combinatorial problem and show how vertex cuts can be used to perform the reduction.

    (joint work with Petko Kitanov, Wil Schilders, and Suzanne Shontz)