Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T22:06:30.791Z Has data issue: false hasContentIssue false

WDM and Directed Star Arboricity

Published online by Cambridge University Press:  05 February 2010

OMID AMINI
Affiliation:
Projet Mascotte, CNRS/INRIA/UNSA, INRIA Sophia-Antipolis, 2004 route des Lucioles BP 93, 06902 Sophia-Antipolis Cedex, France (e-mail: oamini@sophia.inria.fr, fhavet@sophia.inria.fr, fhuc@sophia.inria.fr)
FRÉDÉRIC HAVET
Affiliation:
Projet Mascotte, CNRS/INRIA/UNSA, INRIA Sophia-Antipolis, 2004 route des Lucioles BP 93, 06902 Sophia-Antipolis Cedex, France (e-mail: oamini@sophia.inria.fr, fhavet@sophia.inria.fr, fhuc@sophia.inria.fr)
FLORIAN HUC
Affiliation:
Projet Mascotte, CNRS/INRIA/UNSA, INRIA Sophia-Antipolis, 2004 route des Lucioles BP 93, 06902 Sophia-Antipolis Cedex, France (e-mail: oamini@sophia.inria.fr, fhavet@sophia.inria.fr, fhuc@sophia.inria.fr)
STÉPHAN THOMASSÉ
Affiliation:
LIRMM, 161 rue ADA, Montpellier, France (e-mail: thomasse@lirmm.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A digraph is m-labelled if every arc is labelled by an integer in {1, . . ., m}. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study n-fibre colourings of labelled digraphs. These are colourings of the arcs of D such that at each vertex v, and for each colour α, in(v, α) + out(v, α) ≤ n with in(v, α) the number of arcs coloured α entering v and out(v, α) the number of labels l such that there is at least one arc of label l leaving v and coloured with α. The problem is to find the minimum number of colours λn(D) such that the m-labelled digraph D has an n-fibre colouring. In the particular case when D is 1-labelled, λ1(D) is called the directed star arboricity of D, and is denoted by dst(D). We first show that dst(D) ≤ 2Δ−(D)+1, and conjecture that if Δ−(D) ≥ 2, then dst(D) ≤ 2Δ−(D). We also prove that for a subcubic digraph D, then dst(D) ≤ 3, and that if Δ+(D), Δ−(D) ≤ 2, then dst(D) ≤ 4. Finally, we study λn(m, k) = max{λn(D) | D is m-labelled and Δ−(D) ≤ k}. We show that if m ≥ n, then $\ds \bigl\lceil\frac{m}{n}\bigl\lceil \frac{k}{n}\bigr\rceil + \frac{k}{n} \bigr\rceil\leq \lambda_n(m, k) \leq\bigl\lceil\frac{m}{n}\bigl\lceil \frac{k}{n}\bigr\rceil + \frac{k}{n} \bigr\rceil + C \frac{m^2\log k}{n}$ for some constant C. We conjecture that the lower bound should be the correct value of λn(m, k).

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2010