### Page Content

### to Navigation

## On the S-Labeling Problem

**Prof. Stéphane Vialette**** (****Université Paris-Est Marne-la-Vallée)**

A labeled graph is a graph in which all vertices have distinct labels from the set of integers {1,...,n}. The NP-complete S-labeling problem asks for finding a labeling such that the total sum \sum_{{u, v} \in E} \min{f(u), f(v)} is as small as possible. We present some results devoted to approximating this problem and show that the S-labeling problem is polynomial-time solvable for caterpillar and split graphs.

Date | Speaker | Location | Language |
---|---|---|---|

14.10.2014 16:15 | Stéphane Vialette | TEL 512 | english |