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

2011 Optimization Days

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

Schedule Authors My Schedule

WA5 Théorie des graphes / Graph Theory

May 4, 2011 10:30 AM – 12:10 PM

Location: Demers Beaulne

Chaired by Odile Marcotte

4 Presentations

  • 10:30 AM - 10:55 AM

    Simultaneous Clustering

    • Zhentao Li, presenter, 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.

  • 10:55 AM - 11:20 AM

    Disjoint Paths in Acyclic Planar Graphs

    • Guyslain Naves, presenter, 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)

  • 11:20 AM - 11:45 AM

    Fractional Total Colouring Graphs of Large Maximum Degree

    • Sean Kennedy, presenter, 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.

  • 11:45 AM - 12:10 PM

    Model Order Reductions Through Vertex Cuts

    • Odile Marcotte, presenter, 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)