HEC Montréal, Canada, 2 - 4 mai 2011
Journées de l'optimisation 2011
HEC Montréal, Canada, 2 — 4 mai 2011

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
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
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
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
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)