|
Evènement pour le groupe GT Graphes et Applications
Date | 2010-06-08 10:00-11:00 |
Titre | A linear time algorithm for L(2,1)-labeling of trees |
Résumé | An $L(2,1)$-labeling of a graph $G$ is an assignment $f$
from the vertex set $V(G)$ to the set of nonnegative integers
such that $|f(x)-f(y)|ge 2$ if $x$ and $y$ are adjacent and
$|f(x)-f(y)|ge 1$ if $x$ and $y$ are at distance 2,
for all $x$ and $y$ in $V(G)$. A $k$-$L(2,1)$-labeling is
an $L(2,1)$-labeling $f:V(G)
ightarrow{0,ldots ,k}$,
and the $L(2,1)$-labeling problem asks the minimum $k$,
which we denote by $lambda(G)$, among all possible assignments.
It is known that this problem is NP-hard even for graphs of treewidth 2,
and tree is one of very few classes for which the problem is
polynomially solvable. The running time of the best known algorithm
for trees had been $O(Delta^{4.5} n)$ for more than a decade, and
an $mO(min{n^{1.75},Delta^{1.5}n})$-time algorithm has appeared recently,
where $Delta$ is the maximum degree of $T$ and $n=|V(T)|$,
however, it has been open if it is solvable in linear time.
This is a joint work with Toshimasa Ishii, Toru Hasunuma and Yushi Uno.
|
Lieu | Salle 5, Batiment A29 |
Orateur | Hirotaka Ono |
Url | Department of Informatics, Kyushu University, Japan |
Aucun document lié à cet événement. RetourRetour à l'index
| |