DocumentCode :
2787076
Title :
Minimum number of wavelengths equals load in a DAG without internal cycle
Author :
Bermond, Jean-Claude ; Cosnard, Michel
Author_Institution :
INRIA, Sophia-Antipolis
fYear :
2007
fDate :
26-30 March 2007
Firstpage :
1
Lastpage :
10
Abstract :
Let P be a family of dipaths. The load of an arc is the number of dipaths containing this arc. Let pi(G, P) be the maximum of the load of all the arcs and let w(G, P) be the minimum number of wavelengths (colors) needed to color the family of dipaths P in such a way that two dipaths with the same wavelength are arc-disjoint. Let G be a DAG (directed acyclic graph). An internal cycle is an oriented cycle such that all the vertices have at least one predecessor and one successor in G (said otherwise every cycle contain neither a source nor a sink of G). Here we prove that if G is a DAG without internal cycle, then for any family of dipaths P, w(G, P) = pi(G, P). On the opposite we give examples of DAGs with internal cycles such that the ratio between w(G, P) and pi(G, P) cannot be bounded. We also consider an apparently new class of DAGs, which is of interest in itself, those for which there is at most one dipath from a vertex to another. We call these digraphs UPP-DAGs. For these UPP-DAGs we show that the load is equal to the maximum size of a clique of the conflict graph. We show that if an UPP-DAG has only one internal cycle, then for any family of dipaths w(G, P) = lceilpi(G, P)rceil and we exhibit an UPP-DAG and a family of dipaths reaching the bound. We conjecture that the ratio between w(G, P) and pi(G, P) cannot be bounded.
Keywords :
directed graphs; graph colouring; conflict graph; directed acyclic graph; graph dipath; Add-drop multiplexers; Design optimization; Optical fiber networks; Parallel processing; Telecommunication traffic; Topology; WDM networks; Wavelength assignment; Wavelength division multiplexing; Wavelength routing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International
Conference_Location :
Long Beach, CA
Print_ISBN :
1-4244-0910-1
Electronic_ISBN :
1-4244-0910-1
Type :
conf
DOI :
10.1109/IPDPS.2007.370244
Filename :
4227972
Link To Document :
بازگشت