HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 , Laboratoire I3S - 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 $\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$ of label $l$ 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$.}$
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00132396
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Thursday, May 3, 2007 - 10:36:41 AM
Last modification on : Friday, February 4, 2022 - 3:19:52 AM
Long-term archiving on: : Thursday, September 23, 2010 - 4:02:32 PM

Files

RR-6179.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00132396, version 3
  • ARXIV : 0705.0315

Citation

Omid Amini, Frédéric Havet, Florian Huc, Stéphan Thomassé. WDM and Directed Star Arboricity. [Research Report] RR-6179, INRIA. 2007, pp.20. ⟨inria-00132396v3⟩

Share

Metrics

Record views

420

Files downloads

125