Invited Session Mon.3.H 3005

Monday, 15:15 - 16:45 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Exact and approximation algorithms on graphs


Chair: Frédéric Meunier



Monday, 15:15 - 15:40 h, Room: H 3005, Talk 1

Denis Cornaz
Strengthening Lovász bound for coloring with a new graph transformation

Coauthor: Meurdesoif Philippe


Let α(G) and χ(G) denote the stability number and the clique-partition number of G, respectively. Using a new graph transformation, one constructs a new operator Φ which associates to any graph parameter β such that α(G) ≤ β(G) ≤ χ(G) for all graphs G, a graph parameter Φβ such that α(G) ≤ Φβ(G) ≤ χ(G) for all graphs G. We prove that ϑ(G) ≤ Φϑ(G) and that Φχf(G) ≤ χf(G) for all graphs~G, where ϑ is Lovász theta function and χf is the fractional clique-partition number. Φϑ is unbounded and numerical experiments show that Φϑ is a significant better lower bound for χ than ϑ.



Monday, 15:45 - 16:10 h, Room: H 3005, Talk 2

Frédéric Meunier
A routing problem raised by self-service bike hiring systems

Coauthors: Daniel Chemla, Roberto Wolfler Calvo


Operating bike-sharing systems raises many problems. One of the most natural is the repositioning of the bikes with the help of one or many trucks.
We focus in this talk on the case when there is only one truck. We are given a graph whose vertices model stations. The current repartition of the bikes is known. We wish to move these bikes with the truck in order to reach a target repartition, and we want to realize this task at a minimal cost. The concrete motivation corresponds to the situation encountered at the end of the night, when very few bikes are moving.
A part of the talk will be devoted to special polynomial cases and to approximation algorithms. An efficient method able to solve in practice instances of reasonable size will also be presented: this method combines the exact computation of a natural lower bound and a local search exploiting theoretical properties of the problem. Open questions will also be discussed.



Monday, 16:15 - 16:40 h, Room: H 3005, Talk 3

Henning Bruhn
Clique or hole in claw-free graphs

Coauthor: Akira Saito


Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x from y. As applications we derive an algorithm to verify whether there is a hole through two given vertices as well as an algorithm for the 3-in-a-tree problem in claw-free graphs.


  unsecured loans . The main advantage of Viagra Soft Tablets comparing with other products of this type is its faster on-set effect.