Historique de la collaboration

Les membres de MASCOTTE et de l'école d'informatique de SFU (Simon Fraser University) à Vancouver ont des collaborations très suivies depuis plusieurs années.
Visites de chercheurs de MASCOTTE : J-C. Bermond a passé une année sabbatique (1988) et effectué une dizaine de visites dont un mois en 2003, 2004 et 2005, 2 semaines en 2006 et 3 semaines en 2008, A. Ferreira a effectué plusieurs visites de plus d'un mois, M. Syska y a passé un mois en 1992, 1996, 2004 et 2006 ainsi qu'un séjour post-doctoral de janvier à aout 1993, S. Pérennes y a passé 4 mois en 1998, un mois en 2005 et en 2007, R. Klasing y a passé un mois en 1999, 2004 et 15 jours en 2005 (il est maintenant au LABRI), F. Havet y a passé un mois en 2001, D. Coudert y a passé un mois en 2004 et en 2008, M. Cosnard y a passé un mois en 2007, et D. Mazauric y a effectué un stage de 2 mois en 2008.

Symétriquement J. Peters a passé son année sabbatique 90-91 chez nous, 1 mois en 1998, 2 mois en 2003, 4 mois en 2004, 5 mois en 2005, 1 mois en 2006, 3 semaines en 2007 et 1 mois en 2008. P. Hell passe régulièrement chaque année environ 1 mois (ou 2 mois comme en 2002) au titre de professeur ou chercheur invité. M.-L. Yu est venu de nombreuses fois comme chercheur invité CNRS ou INRIA ou UNSA. Il a passé 9 mois ici en 2001, 3 mois en 2002, en 2003, en 2004, en 2005, en 2007 et en 2008, et 1 mois en 2006. L. Stacho est venu 3 semaines en 2006 et 2 semaines en 2007. D'autres visites plus courtes ont aussi eu lieu.

Une collaboration officielle a été financée par un PICS CNRS-CANADA de 1992 à 95 (le premier PICS franco-canadien du CNRS).
Plusieurs membres de MASCOTTE ont participé à des jurys de thèse à Vancouver (J-C. Bermond a dirigé une thèse) et réciproquement les chercheurs de SFU ont été rapporteurs et/ou membres de plusieurs jurys d'étudiants de MASCOTTE. J. Peters a été membre du comité d'évaluation du programme 1A de l'INRIA en 1999.
Enfin nous avons plus de 30 articles en commun avec eux (voir plus bas).

La collaboration passée a eu pour objectif principal d'appliquer une expertise commune en mathématiques discrètes, et en particulier en théorie des graphes, aux problèmes de conception de réseaux (principes reliant le degré d'un réseau, son diamètre et son nombre de sommet [BHQ92], propriétés structurelles [BHY90a] [BHY90b] [BeHe93] et aux questions liées à la diffusion de l'information dans les réseaux [BHLP92a] [BHLP92b] [BFP95] [BHLP97] [FPP98] [FrPe01] [GHP01]. Sur le plan théorique, elle a contribué a comprendre les phénomènes de diffusion et d'échange total. Sur un plan plus pratique, elle a mis en perspective l'importance des hypothèses de modélisation (commutation de paquets, routage wormhole, réseaux par bus [PeSy96] [BMY00] [BBGH+97] avec comme domaine d'applications le parallélisme.
Les deux projets ont à peu près en même temps réorienté leurs thématiques vers la modélisation et la résolution des problèmes issus des réseaux de télécommunications et investi plus dans les relations industrielles. Au sein de l'école d'informatique de SFU a été crée en septembre 2001 un nouveau groupe (projet) qui travaille de fait sur les mêmes sujets que MASCOTTE. Si durant ces dernière années MASCOTTE a eu tendance à collaborer plus avec des partenaires industriels et des partenaires européens, l'équipe de SFU reste par la qualité de ses chercheurs et les thématiques développées comme la plus voisine de nous et un excellent partenaire pour une équipe associée. Plusieurs chercheurs de MASCOTTE (en particulier ceux recrutés récemment) souhaitent aller régulièrement à Vancouver et de manière réciproque plusieurs chercheurs canadiens souhaitent profiter d'années sabbatiques pour venir ici.

1. J.-C. Bermond, R. Correa, and M.-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Discrete Mathematics, 2008, to appear.
   Note: A preliminary version has been presented at CIAC06. [WWW ] [PDF ]

   Abstract:

   We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being transmitted simultaneously. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d?1, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. In this paper, we suppose that each node has one unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem when the network is a path and the destination node is either at one end or at the center of the path. These protocols are shown to be optimal for any d in the first case, and for 1?d?4, in the second case.



2. F. Havet and M.-L. Yu. $(p,1)$-total labelling of graphs. Discrete Mathematics, 308(4):496--513, February 2008. [PDF ]

   Abstract:

   A $(p,1)$-total labelling of a graph $G$ is an assignment of integers to $V(G)\cup E(G)$ such that: (i) any two adjacent vertices of $G$ receive distinct integers, (ii) any two adjacent edges of $G$ receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least $p$ in absolute value. The {\it span} of a $(p,1)$-total labelling is the maximum difference between two labels. The minimum span of a $(p,1)$-total labelling of $G$ is called the {\it $(p,1)$-total number} and denoted by $\lambda_p^T(G)$. We provide lower and upper bounds for the $(p,1)$-total number. In particular, generalizing the Total Colouring Conjecture, we conjecture that $\lambda_p^T\leq \Delta+ 2p - 1$ and give some evidences to support it. Finally, we determine the exact value of $\lambda^T_p(K_n)$, except for even $n$ in the interval $[p+5, 6p2-10p+4]$ for which we show that $\lambda_p^T(K_n) \in n+2p-3, n+2p-2$.



3. J.-C. Bermond and M-L. Yu. Optimal gathering algorithms in multi-hop radio tree networks with interferences. In ADHOC-NOW 2008, volume 5198 of Lecture Notes in Computer Science, pages 204-217, September 2008. Springer-Verlag. [PDF ]

   Abstract:

   We study the problem of gathering information from the nodes of a multi-hop radio network into a pre-defined destination node under the interference constraints. In such a network, a message can only be properly received if there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes and the edges, the possible communications. The interference constraint is modeled by a fixed integer $d_I \geq 1$, which implies that nodes within distance $d_I$ in the graph from one sender cannot receive messages from another node. In this paper, we suppose that it takes one unit of time (slot) to transmit a unit-length message. A step (or round) consists of a set of non interfering (compatible) calls and uses one slot. We present optimal algorithms that give minimum number of steps (delay) for the gathering problem with buffering possibility, when the network is a tree, the root is the destination and $d_I =1$. In fact we study the equivalent personalized broadcasting problem instead.



4. D. Mazauric. Conception et analyse d'algorithmes distribués d'ordonnancement des transmissions dans les réseaux sans-fil, Juin 2008. [PDF ]


5. J-C. Bermond, D. Coudert, and J. Peters. Online multihop traffic grooming on the path with bounded number of ADMs per node.
   Note: Manuscript, 2008.

   Abstract:

   We investigate online multihop traffic grooming when the physical topology is a path. Each node has a bounded number of ADMs and hops have fixed sizes. We provide bounds on the size of the network allowing to handle any traffic pattern, independently of the routing algorithm.



6. J-C. Bermond and J. Peters. Optimal Gathering in Radio Grids with Interference.
   Note: Submitted to Discrete Mathematic, 2008.


7. S. Perennes and J. Peters. Modelling Peer-Assisted Content Distribution Systems.
   Note: Manuscript, 2008.

1. J.-C. Bermond, A. Ferreira, S. Pérennes, and J. Peters. Neighbourhood Broadcasting in Hypercubes. SIAM Journal on Discrete Mathematics, 21(4):823-843, 2007. [PDF ]

   Abstract:

   In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of $N$ nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with $N$ nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes.



2. J.-C. Bermond and M.-L. Yu. Vertex disjoint routings of cycles over tori. Networks, 49(3):217-225, 2007. [PDF ]


3. J-C. Bermond, R. Correa, and M-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Technical report inria-00168162, HAL, August 2007. [WWW ] [PDF ]

1. R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing Incremental Sequences in Graphs. Algorithmic Operations Research, 1(2), 2006.


2. J-C. Bermond, R. Correa, and M-L. Yu. Gathering algorithms on paths under interference constraints. In 6th Conference on Algorithms and Complexity, Roma,Italy, pages 115-126, May 2006. [PDF ]

1. J-C. Bermond and J. Peters. Efficient Gathering in Radio Grids with Interference.. In ALGOTEL, pages 103-106, 2005. [PDF ]


2. R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing Incremental Sequences in Graphs. Technical report, INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR, 2005. [PDF ] [POSTSCRIPT ]

1. J-C. Bermond, C.J. Colbourn, A. Ling, and M-L. Yu. Grooming in unidirectional rings : $K_4 -e$ designs. Discrete Mathematics, Lindner's Volume, 284(1-3):57-62, 2004. [POSTSCRIPT ]


2. J-C. Bermond, A. Ferreira, S. Perennes, and J. Peters. Neighbourhood Broadcasting in Hypercubes. Technical report, SFU-CMPT-TR 2004-12, 2004.
   Note: Submitted to SIAM JDM. [PDF ]

1. R. Balakhrishnan, J-C. Bermond, P. Paulraja, and M.L. Yu. On Hamilton cycle decompositions of the tensor product of complete graphs. Discrete Mathematics, 268:49-58, 2003.


2. J-C. Bermond, D. Coudert, and M-L. Yu. On DRC-covering of $K_n$ by Cycles. Journal of Combinatorial Designs, 11(3):100-112, 2003. [PDF ] [POSTSCRIPT ]

   Abstract:

   This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on sub-networks which are protected independently from each other. The problem can be stated as follows~: for a given graph $G$, find a cycle covering of the edge set of $K_n$, where $V(K_n) = V(G)$, such that each cycle in the covering satisfies the disjoint routing constraint (DRC), relatively to $G$, which can be stated as follows~: to each edge of $K_n$ we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where $G = C_n$, a ring of size $n$ and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4.

1. F. Havet and M-L. Yu. On $(d,1)$-total labelling of graphs. Rapport de recherche INRIA RR-4650, Projet MASCOTTE, Sophia Antipolis, November 2002.

1. L. Gargano, P. Hell, and S. Pérennes. Coloring All Directed Paths in a Symmetric Tree, with an Application to Optical Networks. Journal of Graph Theory, 38(4):183--196, 2001.

1. J-C. Bermond, S. Marshall, and M.-L. Yu. Improved bounds for gossiping in mesh-bus networks. Journal Of Interconnection Networks, 1(1):1-19, 2000.

1. B. Beauquier, P. Hell, and S. Pérennes. Optimal wavelength-routed multicasting. Discrete Appl. Math., 84(1-3):15--20, 1998.


2. S. Fujita, S. Pérennes, and J.G. Peters.. Neighbourhood Gossiping in Hypercubes. Parallel Processing Letters, 8:189--195, 1998.

1. L. Gargano, P. Hell, and S. Pérennes. Colouring paths in directed symmetric trees with applications to WDM routing. In Automata, languages and programming (Bologna, 1997), volume 1256 of Lecture Notes in Comput. Sci., pages 505--515. Springer, Berlin, 1997.


2. J-C. Bermond, H. A. Harutyunyan, A. L. Liestman, and S. Pérennes. A Note on the Dimensionality of Modified Knödel Graphs. International Journal of Foundations of Computer Science, 8(2):109--116, 1997.


3. B. Beauquier, J-C. Bermond, L. Gargano, P. Hell, S. Pérennes, and U. Vaccaro. Graph problems arising from wavelength--routing in all--optical networks. In WOCS97, April 1997.

1. J.G. Peters and M. Syska. Circuit-Switched Broadcasting in Torus Networks. IEEE Trans. on Parallel and Distributed Systems, 7(3):246--255, 1996.

1. J.-C. Bermond, P. Fraigniaud, and J.G. Peters. Antepenultimate broadcasting. Networks, 26(3):125--137, 1995.

1. M. Cosnard, A. Ferreira, and J. Peters, editors. Parallel and Distributed Computing -- Theory and Practice, volume 805 of Lecture Notes in Computer Science. Springer-Verlag, 1994.

1. J.-C. Bermond and P. Hell. On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs. Journal of Graph Theory, 17(5):647--655, 1993.

1. J.-C. Bermond, P. Hell, A.L. Liestman, and J.G. Peters. Sparse broadcast graphs. Disc. Appl. Math., 36:97--130, 1992.


2. J.-C. Bermond, P. Hell, A.L. Liestman, and J.G. Peters. Broadcasting in bounded degree graphs. SIAM Journal on Disc. Math., 5(1):10--24, 1992.


3. J-C. Bermond, P. Hell, and J-J. Quisquater. Construction of large packet radio networks. Parallel Processing Letters, 2(1):3-12, 1992.

1. A. Ferreira and J. Peters. Finding the smallest path in a rectilinear polygon on a hypercube multiprocessor. In Proceedings of the Third Canadian Conference on Computational Geometry -- CCCG'91, Vancouver (Ca), pages 162-165, 1991.

1. B. Alspach, J-C. Bermond, and D. Sotteau. Decomposition into cycles. I. Hamilton decompositions. In Cycles and rays (Montreal, PQ, 1987), volume 301 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 9--18. Kluwer Acad. Publ., Dordrecht, 1990.


2. J-C. Bermond, K. Heinrich, and M-L. Yu. On resolvable mixed path designs. European J. Combin., 11(4):313--318, 1990.


3. J.-C. Bermond, K. Heinrich, and M.-L. Yu. Existence of resolvable path designs. European J. Combin., 11(3):205--211, 1990.

This document was translated from BibT_EX by bibtex2html