HEC Montréal, Canada, May 2  4, 2011
2011 Optimization Days
HEC Montréal, Canada, 2 — 4 May 2011
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
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
We consider the problem of finding arcdisjoint 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
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
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 socalled 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)