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

Directed acyclic graphs with the unique dipath property

Jean-Claude Bermond 1 Michel Cosnard 1 Stéphane Pérennes 1
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
Abstract : Let PP be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let pi (G,PP) be the maximum of the load of all the arcs and let w(G, PP) be the minimum number of wavelengths (colors) needed to color the family of dipaths PP in such a way that two dipaths with the same wavelength are arc-disjoint. There exist DAGs such that the ratio between w(G, PP) and pi (G,PP) cannot be bounded. 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 contains neither a source nor a sink of G). We prove that, for any family of dipaths PP, w(G, PP = pi(G,PP) if and only if G is without internal cycle. We also consider a 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 prove that the ratio between w(G, PP) and pi (G,PP) cannot be bounded (a result conjectured in an other article). For that we introduce ''good labelings'' of the conflict graph associated to G and PP, namely labelings of the edges such that for any ordered pair of vertices (x,y) there do not exist two paths from $x$ to $y$ with increasing labels.
Document type :
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

Contributor : Jean-Claude Bermond Connect in order to contact the contributor
Submitted on : Wednesday, August 10, 2011 - 10:06:04 PM
Last modification on : Friday, February 4, 2022 - 3:18:03 AM
Long-term archiving on: : Sunday, December 4, 2016 - 11:35:46 AM


Files produced by the author(s)


  • HAL Id : inria-00387085, version 2



Jean-Claude Bermond, Michel Cosnard, Stéphane Pérennes. Directed acyclic graphs with the unique dipath property. [Research Report] Inria. 2009, pp.19. ⟨inria-00387085v2⟩



Record views


Files downloads