WDM and Directed Star Arboricity

Omid Amini 1 Frédéric Havet 1 Florian Huc 1 Stéphan Thomassé 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A digraph is {\it $m$-labelled} if every arcs is labelled by an integer in $\{1, \dots ,m\}$. Motivated by wavelength assignment for multicasts in optical star networks, we study {\it $n$-fiber colourings} of labelled digraph which are colourings of the arcs of $D$ such that at each vertex $v$, for each colour in $\lambda$, $in(v,\lambda)+out(v,\lambda)\leq n$ with $in(v,\lambda)$ the number of arcs coloured $\lambda$ entering $v$ and $out(v,\lambda)$ the number of labels $l$ such that there exists an arc leaving $v$ coloured $\lambda$. One likes to find the minimum number of colours $\lambda_n(D)$ such that an $m$-labbelled digraph $D$ has an $n$-fiber colouring. In the particular case, when $D$ is $1$-labelled then $\lambda_n(D)$ is the {\it directed star arboricty} of $D$, denoted $dst(D)$. We first show that $dst(D)\leq 2\Delta^-(D)+1$ and conjecture that if $\Delta^-(D)\geq 2$ then $dst(D)\leq 2\Delta^-(D)$. We also prove that if $D$ is subcubic then $dst(D)\leq 3$ and that if $\Delta^+(D), \Delta^-(D)\leq 2$ then $dst(D)\leq 4$. Finally, we study $\lambda_n(m,k)=\max\{\lambda_n(D) \tq D \mbox{ is $m$-labelled} \et \Delta^-(D)\leq k\}$. We show that if $m\geq n$ then $\ds \left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil\leq \lambda_n(m,k) \leq\left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil + C \frac{m^2\log k}{n} \mbox {\ \ \ \ \ for some constant $C$.}$
Type de document :
Article dans une revue
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2010, 19, pp.161-182
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00512776
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:41:14
Dernière modification le : mardi 21 novembre 2017 - 01:23:44
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:52:10

Fichier

dst.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00512776, version 1

Collections

Citation

Omid Amini, Frédéric Havet, Florian Huc, Stéphan Thomassé. WDM and Directed Star Arboricity. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2010, 19, pp.161-182. 〈lirmm-00512776〉

Partager

Métriques

Consultations de la notice

624

Téléchargements de fichiers

191