Seminars are given every Friday from 2:00 to 3:00 in room 178. You are welcome 10 minutes earlier for tea, coffee and cake.

In order to receive the announcements, just send an email to with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.

Next talks:

Vendredi 31 janvier 2020 - Packing and covering balls in graphs excluding a minor - Carole Muller (Université Libre de Bruxelles, Belgique).

Given a graph G, the ball centered at vertex v of radius r is the set containing all vertices at distance at most r from v. We prove that for every integer t > 0 there exists a constant c_t such that for every K_t-minor-free graph G, and every set S of balls in G, the minimum size of a set of vertices of G intersecting all the balls of S is at most c_t times the maximum number of vertex-disjoint balls in S. This was conjectured by Chepoi in 2007 in the special case of planar graphs and of balls having the same radius. This is joint work with Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, and François Pirot.

Vendredi 31 janvier 2020 à 15h - Approximation algorithms for the p-hub center routing problem in parameterized metric graphs - Ling-Ju Hung (National Taipei University of Business, Taiwan).

Let G = (V, E, w) be a ∆β-metric graph with a distance function w(·, ·) on V such that w(v, v) = 0, w(u, v) = w(v, u), and w(u, v) ≤ β · (w(u, x) + w(x, v)) for all u, v, x ∈ V . Given a positive integer p, let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C ⊂ V form a clique of size at most p in H, vertices (non-hubs) in V \C form an independent set in H, and each non-hub v ∈ V \ C is adjacent to exactly one hub in C. Define dH(u, v) = w(u, f(u)) + w(f(u), f(v)) + w(v, f(v)) where f(u) and f(v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w(u, f(u)) = 0. Let r(H) = P u,v∈V dH(u, v) be the routing cost of H. The Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H of G such that r(H) is minimized. In this talk, we will show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in ∆β-metric graphs for any β > 1/2. We give 2β-approximation algorithms running in time O(n 2 ) for any β > 1/2 where n is the number of vertices in the input graph. Finally, we show that the approximation ratio of our algorithms is at least Ω(β), and we examine the structure of any potential o(β)-approximation algorithm.

Vendredi 7 février 2020 - New optimization variant of combinatorial reconfiguration - Haruka Mizuta (Graduate School of Information Sciences, Tohoku University, Sendai, Japan).

Combinatorial reconfiguration asks for a step-by-step transformation on the solution space formed by feasible solutions of a combinatorial problem. This framework has been applied to many central combinatorial problems, such as Satisfiability, Independent Set, Coloring, and Matching. In most of the known work, we are given two feasible solutions as an input, and wish to determine whether they are reachable on the solution space. Recently, we proposed a new variant of combinatorial reconfiguration. In this variant, we are given only one feasible solution as an input, and wish to find a most desirable solution which is reachable from the given one. In this talk, we start with a brief introduction of combinatorial reconfiguration, and then explain our new variant by applying it to Independent Set and Dominating Set.



GT Graphs and Optimization


 Previous Years

edit SideBar