To get a current list, please request a desktop version of this page with (java)scripts enabled.

To automatically add seminars to your calendar application, you can register the following calendar (ICS format):

Next seminar

Past seminars

Nicolas Nisse (COATI) — 05/03/2013

Weighted Coloring on Trees

Joint work: Julio Araujo, Nicolas Nisse, Stéphane Pérennes

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a vertex-weighted graph {$G$} as the smallest weight of a proper coloring of {$G$} (1997). If each node of a graph has weight 1, the weighted chromatic number of a graph coincides with its chromatic number. Therefore, the problem of computing the weighted chromatic number is NP-complete in general graphs. This problem is even NP-complete in some particular graph classes as bipartite graphs. Escoffier et al. presented a polynomial-time approximation scheme for computing the weighted chromatic number of partial {$k$}-trees (2006), and Kavitha and Mestre provided polynomial-time algorithms for some sub-classes of trees (2009). Surprisingly, the time-complexity of computing this parameter in trees is still open.

We show that, under the Exponential Time Hypothesis (ETH), the best algorithm to compute the weighted chromatic number of a tree {$T$} has time-complexity {$n^{\Theta(\log n)}$}, where {$n$} the number of vertices of {$T$}. Our result mainly relies on proving that it is hard to combine colorings of disjoint induced subgraphs (or connected components?) of the input graph {$G$}, in order to find a coloring of {$G$} with bounded weight.

Brigitte Jaumard (Concordia University, Montréal, Canada) — 21/02/2013

Path vs. Cutset Approaches for the Design of Virtual Survivable Topologies

Multi-layer optical networks have recently evolved towards IP-over-WDM networks. Therein, in order to avoid protection/restoration redundancies against either single or multiple failures, synergies need to be developed between IP and optical layers in order to reduce the costs and the energy consumption of the future IP-over-WDM networks. We propose two new optimization models. The first one is an enhanced cutset model, relying on a column generation reformulation. The second one is a path model, based on a multi-flow formulation. Both models can solve exactly most benchmark instances, which were only solved heuristically so far.

Arie M.C.A. Koster (RWTH Aachen, Germany) — 12/02/2013

A crash course in Robust Optimization


Fatima Zahra Moataz (COATI) — 05/02/2013

Electrical Flows for a faster Approximation of Maximum Flow in Undirected Graphs

Maximum Flow is a widely studied broadly applied problem which algorithms are resisting improvement for about a decade. Christiano, Kelner, Madry, Spielman and Teng designed in 2010 the fastest known algorithm for approximating Max Flow. They used a new approach based on solving a sequence of elecrical flow problems. This seminar is a presentation of their method and results.

Comments are closed