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)