Sie sind hier

## 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