webmaster 
Equipe Associée : RESEAUXCOM
Home   Historique Activité Bibliographie


2008 2007 2006 2005 2004 2003 2002 2001 2000
1999 1998 1997 1996 1995 1994 1993 1992 1991
1990 no year

2008
  1. 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$.

  2. 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.

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

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

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

2007
  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 and M. Cosnard. Minimum number of wavelengths equals load in a DAG without internal cycle. In Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, Long Beach, CA, U.S.A., pages 1-10, March 2007. [PDF ]

  4. 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 ]

2006
  1. J.-C. Bermond and D. Coudert. Handbook of Combinatorial Designs (2nd edition), volume 42 of Discrete mathematics and Applications, chapter VI.27, Grooming, pages 494-496. Chapman & Hall- CRC Press, editors C.J. Colbourn and J.H. Dinitz, November 2006. [WWW ] [PDF ]
    Abstract: State-of-the-art on traffic grooming with a design theory approach

  2. Handbook of Algorithms for Wireless and Mobile Computing, chapter Routing and Traversal via Location Awareness in Ad-Hoc Networks, pages 163--179. Chapman and Hall/CRC Press, ed. Azzedine Boukerche edition, 2006.
    Note: ISBN 1-58488-465-7.

  3. A.Gupta, J. Manuch, and L. Stacho. Fault tolerant forwarding and optical indexes: a design theory approach. Journal of Combinatorial designs, 14(1):25-40, 2006.

  4. J.-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Pérennes. Hardness and approximation of Gathering in static radio networks. Parallel Processing Letters, 16(2):165--183, 2006. [PDF ] [POSTSCRIPT ]

  5. E. Chavez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Route Discovery with Constant Memory in Oriented Planar Geometric Networks. Networks, 2006.

  6. D. Coudert, P. Datta, S. Perennes, H. Rivano, and M-E. Voge. Shared Risk Resource Group: Complexity and Approximability issues. Parallel Processing Letters, 2006, to appear.

  7. A. Goldman, J.G. Peters, and D. Trystram. Exchanging Messages of Different Sizes. Journal of Parallel and Distributed Computing, 66(1):1--18, 2006.

  8. A. Gupta, J. Manuch, and L. Stacho. Fault tolerant forwarding and optical indexes: a design theory approach. Journal of Combinatorial Designs, 14:25--40, 2006.

  9. S. Huang, R. Dutta, and G. N. Rouskas. Traffic Grooming in Path, Star, and Tree Networks: Complexity, Bounds, and Algorithms. IEEE Journal on Selected Areas in Communications, 24(4):66-82, April 2006. [PDF ]

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

  11. 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 ]

  12. J-C. Bermond, M. Cosnard, D. Coudert, and S. Perennes. Optimal Solution of the Maximum All Request Path Grooming Problem. In Advanced International Conference on Telecommunications (AICT), 2006. IEEE. [PDF ]

  13. J.-C. Bermond, D. Coudert, X. Muñoz, and I. Sau. Traffic Grooming in Bidirectional WDM ring networks. In IEEE/COST 293 annual conference on GRAphs and ALgorithms in communication networks, volume 3, pages 19--22, June 2006. [PDF ]

  14. J.-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Pérennes. Gathering in specific radio networks. In Huitièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06), Trégastel, France, pages 85--88, May 2006. [WWW ] [POSTSCRIPT ]

  15. J.-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Pérennes. Hardness and approximation of Gathering in static radio networks. In FAWN06, Pisa, Italy, pages 75--79, March 2006. [WWW ] [POSTSCRIPT ]

  16. V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie. An approximation algorithm for the Wireless Gathering Problem. In SWAT, 2006.

  17. E. Chavez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. In 7th Latin American Theoretical Informatics Symposium (LATIN'06), Valdivia, Chile, March 2006.

  18. D. Coudert, S. Perennes, H. Rivano, and M-E. Voge. Shared Risk Resource Groups and Survivability in Multilayer Networks. In IEEE-LEOS ICTON / COST 293 GRAAL, volume 3, pages 235-238, June 2006.
    Note: Invited Paper. [PDF ]

  19. A. Faragó. A Graph Theoretic Model for Complex Network Failure Scenarios. In INFORMS, 2006.

  20. Michele Flammini, Luca Moscardelli, Mordechai Shalom, and Shmuel Zaks. Approximating the Traffic Grooming Problem in Tree and Star Networks. In WG, 2006. [PDF ]

  21. Michele Flammini, Mordechai Shalom, and Shmuel Zaks. On Minimizing the Number of ADMs in a General Topology Optical Network. In DISC, 2006. [PDF ]

  22. Michele Flammini, Mordechai Shalom, and Shmuel Zaks. On Minimizing the Number of ADMs - Tight Bounds for an Algorithm Without Preprocessing. In CAAN, 2006. [PDF ]

  23. L. Gargano and A.A. Rescigno. Optimally Fast Data Gathering in Sensor Networks. In LNCS, editor, 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), volume 4162, pages 399-411, 2006. Springer Verlag.

  24. E. Kranakis, T. Mott, and L. Stacho. On-Line Routing in Quasi-Planar and Quasi-Polyhedral Graphs. In 2nd IEEE PerCom Workshop on Pervasive Wireless Networking (PWN'06), Pisa, Italy, March 2006.

  25. N. Obradovic, J. Peters, and G. Ruzic. Multiple Communication Trees of Optimal Circulant Graphs with Two Chord Lengths.
    Note: Submitted to Discrete Applied Mathematics, 2006.

  26. J.G. Peters, C. Rapine, and D. Trystram. Small Depth Arc-Disjoint Spanning Trees in Two-Dimensional Toroidal Meshes.
    Note: Submitted to Journal of Interconnection Networks, 2006.

2005
  1. J-C. Bermond, C. Colbourn, D. Coudert, G. Ge, A. Ling, and X. Muñoz. Traffic Grooming in Unidirectional WDM Rings With Grooming Ratio C=6. SIAM Journal on Discrete Mathematics, 19(2):523-542, 2005.

  2. B. Chen, G. N. Rouskas, and R. Dutta. Traffic Grooming in WDM Ring Networks to Minimize the Maximum Electronic Port Cost. Optical Switching and Networking, 2(1):1-18, May 2005. [PDF ]

  3. N. Obradovic, J. Peters, and G. Ruzic. Reliable Broadcasting in Double Loop Networks. Networks, 46(2):88--97, 2005.

  4. N. Obradovic, J. Peters, and G. Ruzic. Minimum Chromaticity of Circulant Graphs. Discrete Mathematics, 299(1-3):288--296, 2005.

  5. J-C. Bermond, L. Braud, and D. Coudert. Traffic Grooming on the Path. In 12th International Colloquium on Structural Information and Communication Complexity -- SIROCCO, Le Mont Saint-Michel, France, pages 34-48, May 24-26 2005. LNCS 3499. [PDF ]

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

  7. Michele Flammini, Luca Moscardelli, Mordechai Shalom, and Shmuel Zaks. Approximating the Traffic Grooming Problem. In ISAAC, 2005. [PDF ]

  8. Mordechai Shalom and Shmuel Zaks. Minimizing the Number of ADMs in SONET Rings with Maximum Throughput.. In SIROCCO, pages 277-291, 2005. [PDF ]

  9. S. Yuan, S. Varma, and J.P. Jue. Minimum-Color Path Problems for Reliability in Mesh Networks. In IEEE InfoCom, volume 4, pages 2658-2669, 2005.
    Note: 59-04.

  10. 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 ]

  11. C. Lepelletier. Problèmes de charge et de longueur d'onde sur des réseaux tolérants des pannes. Mémoire de DEA, 3 mois, encadrants J.-C. Bermond and S. Bessy, DEA MDFI, Marseille, 2005.

  12. N. Obradovic, J. Peters, and G. Ruzic. Efficient Domination in Circulant Graphs with Two Chord Lengths.
    Note: Submitted to Information Processing Letters, 2005.

2004
  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. C. Florens, M. Franceschetti, and R.J. McEliece. Lower bounds on data collection time in sensory networks. IEEE Journal on Selected Areas in Communications, 22(6):1110-1120, 2004.
    Note: ISSN 0733-8716.

  3. P. Datta and A.K. Somani. Diverse Routing for Shared Risk Resource Groups (SRRG) failu res in WDM Optical Networks. In IEEE BroadNets, pages 120- 129, October 2004.

  4. Mordechai Shalom and Shmuel Zaks. A 10/7 + epsilon Approximation for Minimizing the Number of ADMs in SONET Rings. In BROADNETS, pages 254-262, 2004. [PDF ]

  5. 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 ]

  6. R. Klasing, N. Morales, and S. Perennes. On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands. Technical report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, December 2004. [PDF ] [POSTSCRIPT ]

2003
  1. H. Rivano. Algorithmique et télécommunications : Coloration et multiflot approchés et applications aux réseaux d'infrastructure. PhD thesis, Université de Nice-Sophia Antipolis, November 2003.

  2. 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.

  3. J-C. Bermond and S. Ceroi. Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3. Networks, 41(2):83-86, 2003.

  4. 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.

  5. J.-C. Bermond, N. Marlin, D. Peleg, and S. Pérennes. Directed Virtual Path Layout in ATM networks. Theoretical Computer Science, 291:3-28, 2003.

  6. A. Clementi, A. Ferreira, P. Penna, S. Perennes, and R. Silvestri. The Minimum Range Assignment Problem on Linear Radio Networks. Algorithmica, 35(2):95--110, 2003.

  7. A. Ferreira, S. Perennes, A. W. Richa, H. Rivano, and N. Stier. Models, Complexity and Algorithms for the Design of Multi-fiber WDM Networks. Telecommunication Systems, 24(2):123-138, October 2003.

  8. O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick. The SONET edge-partition Problem. Networks, 41(1):13 - 23, January 2003. [PDF ]

  9. Q. Gu and S. Peng. Multi-hop all-to-all broadcast on WDM optical networks. IEEE trans. on Parallel and Distributed Systems, pp 477-486, May 2003.

  10. Q. Gu and S. Peng. Multi-hop routing on WDM Optical Butterfly Networks. SPIE/Kluwer Optical Networks Magazine, 4(4):83-91, 2003.

  11. J.-C. Bermond and D. Coudert. Traffic Grooming in unidirectional WDM ring networks using design theory. In ICC 2003, IEEE International Conference on Communications, 11-15 May 2003.

  12. J.-C. Bermond, D. Coudert, and X. Munoz. Traffic grooming in Unidirectional WDM Ring Networks: the all-to-all unitary case. In ONDM 03, 7th IFIP Working Conference on Optical Network Design and Modelling, pages 1135-1153, 3-5 February 2003.

  13. J-C. Bermond, O. DeRivoyre, S. Perennes, and M. Syska. Groupage par tubes. In Conference ALGOTEL2003, Banyuls, May 2003, pages 169-174, 2003.

  14. P. Berthomé, M. Diallo, and A. Ferreira. Generalized Parametric Multi-Terminal Flows Problem. In Proceedings of WG'03, volume 2880 of Lecture Notes in Computer Science, pages 71-80, June 2003. Springer Verlag.

  15. M. Bouklit, D. Coudert, J-F. Lalande, C. Paul, and H. Rivano. Approximate multicommodity flow for WDM networks design. In J. Sibeyn, editor, SIROCCO 10, number 17 of Proceedings in Informatics, Umea, Sweden, pages 43--56, 2003. Carleton Scientific. [PDF ] [POSTSCRIPT ]

  16. A. Clementi, G. Huiban, G. Rossi, and Y. Verhoeven. On the Approximation Ratio of the MST-based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks. In International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, pages 222a, 2003. IEEE CS Press.

  17. A. Ferreira, S. Perennes, A. W. Richa, H. Rivano, and N. Stier. On the design of multifiber WDM networks. In Proceedings of the 10-th International Conference on Telecommunications -- ICT'2003, volume I, Tahiti, pages 12--18, 2003. IEEE.

  18. Q. Gu and Y. Wang. Efficient algorithm for embedding hypergraphs in a cycle. In 10th International Conference on High Performance Computing (HiPC03), December 2003.

  19. A. Laugier and S. Petat. Network Design and b-matching. In Proc. of International Network Optimization Conference, pages 374--379, 2003.

  20. T. Tocker, E. Altman, J. Galtier, C. Touati, B. Fabre, I. Buret, and C. Guiraud. Slot allocation in a TDMA satellite system: simulated annealing approach. In Proceedings of AIAA International Communication Satellite Systems Conference and Exhibit, Yokohama, Japan, April 2003.

  21. C. Touati, E. Altman, and J. Galtier. Radio Planning in Multibeam Geostationary Satellite Networks. In Proceedings of AIAA International Communication Satellite Systems Conference and Exhibit, Yokohama, Japan, April 2003.

2002
  1. S. Choplin. Dimensionnement de réseaux virtuels de télécommunication. PhD thesis, Université de Nice - Sophia Antipolis, novembre 2002. [WWW ]

  2. J-C. Bermond, E. Darrot, and O. Delmas. Design of Fault Tolerant On-Board Networks in Satellites. Networks, 40:202--207, 2002.

  3. D. Coudert, A. Ferreira, and S. Pérennes. Isomorphisms of the De Bruijn Digraph and Free-Space Optical Networks. Networks (Wiley-Interscience), 40(3):155-164, October 2002. [PDF ] [POSTSCRIPT ]

  4. F. Havet and J. Zerovnik. Finding a Five Bicolouring of a Triangle-Free Subgraph of the Triangular Lattice. Discrete Mathematics, 244:103--108, 2002.

  5. X. Liu and Q. Gu. Multicasts on WDM all-optical butterfly networks. Journal of Information Science and Engineering, 18(6):1049-1058, 2002.

  6. J-C. Bermond, S. Choplin, and S. Pérennes. Hierarchical Ring Network Design. In 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO'02), pages 1--16, 2002. Carleton Scientific.

  7. D. Coudert and H. Rivano. Lightpath assignment for multifibers wdm optical networks with wavelength translators. In IEEE Globecom, 2002.

  8. Q. Gu. On-line permutation routing on WDM all-optical networks. In Proc. of the 2002 International Conference on Parallel Processing (ICPP02),, pages 419-426, 2002.

  9. G. Huiban, S. Pérennes, and M. Syska. Traffic Grooming in WDM Networks with Multi-Layer Switches. In IEEE ICC, New-York, April 2002.

  10. B. Beauquier, S. Pérennes, and M. Syska. Efficient Access to Optical Bandwidth, Routing and Grooming in WDM Networks: state-of-the-art survey. IST CRESCCO report, Projet MASCOTTE(CNRS/INRIA/UNSA), Sophia Antipolis, July 2002.

  11. 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.

2001
  1. A. Ferreira and D. Krob, editors. Mobile Networks & Applications (MONET) -- Special Issue on Discrete Algorithms and Methods for Mobile Computing and Communications. ACM/Baltzer, 2001.

  2. D. Coudert. Algorithmique et optimisation de réseaux de communications optiques. PhD thesis, Université de Nice Sophia-Antipolis (UNSA), December 2001.

  3. B. Beauquier, O. Delmas, and S. Pérennes. Tight Bounds for Broadcasting in the Linear Cost Model. Journal Of Interconnection Network, 2(2):175--188, 2001.

  4. A. Ferreira, J. Galtier, J-N. Petit, and H. Rivano. Re-routing algorithms in a meshed satellite constellation. Annals of Telecommunications, 56(3/4):169--174, 2001.

  5. P. Fraigniaud and J.G. Peters. Minimum Linear Gossip Graphs and Maximal Linear $(\Delta,k)$-Gossip Graphs. Networks, 38:150--162, 2001.

  6. 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.

  7. H. Harutyunyan and A. L. Liestman. k-Broadcasting in Trees. Networks, 38:163-168, 2001.

  8. H. Harutyunyan and A. L. Liestman. Improved Upper and Lower Bounds for k-Broadcasting. Networks, 37:94-101, 2001.

  9. F. Havet. Channel Assignement and Multicolouring of the Induced Subgraphs of the Triangular Lattice. Discrete Mathematics, 233:219--231, 2001.

  10. C. Laforest, A. L. Liestman, T. Shermer, and D. Sotteau. Edge Disjoint Spanners of Complete Bipartite Graphs. Discr. Math., 234:65-76, 2001.

  11. B. Awerbuch, P. Berenbrink, A. Brinkmann, and C. Scheideler. Simple Routing Strategies for Adversarial Systems. In IEEE FOCS, pages 158-167, 2001.

  12. P. Berenbrink, T. Friedetzky, and L. Goldberg. The Natural Work-Stealing Algorithm is Stable. In Proceedings of the 42th IEEE Symposium on Foundations of Computer Science (FOCS), pages 178-187, 2001.

  13. J-C. Bermond, L. Chacon, D. Coudert, and F. Tillerot. A Note on Cycle Covering. In Proc. of the 13th ACM Symposium on Parallel Algorithms and Architectures -- SPAA, Crete Island, Greece, pages 310--311, jul # 3--6, 2001.

  14. I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, and H. Rivano. Fractional Path Coloring with Applications to WDM Networks. In F. Orejas, P. G. Spirakis, and J. van Leeuwen, editors, Proc. of the 28th ICALP, volume 2076 of Lecture Notes in Computer Science, Crete, Greece, pages 732--743, July 2001. Springer-Verlag. [WWW ]

  15. J. Galtier and A. Oliveira. A proposal to study satellite constellation routing via classical linear programming methods. In 43rd conference of the Canadian Operations Research Society, 2001.

  16. P. Gvozdjak and J.G. Peters. Modelling Links in Inclined LEO Satellite Networks. In International Colloquium on Structural Information and Communication Complexity -- SIROCCO, Vall de Nuria, Spain, pages 195--208, June 2001. Carleton Scientific.

2000
  1. B. Beauquier. Communications dans les réseaux optiques par multiplexage en longueur d'onde. PhD thesis, Université de Nice-Sophia Antipolis -- STIC, January 2000.

  2. J-C. Bermond, L. Gargano, S. Pérennes, A. A. Rescigno, and U. Vaccaro. Efficient Collective Communication in Optical Networks. Theoretical Computer Science, 233(1--2):165--189, February 2000. [WWW ]

  3. 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.

  4. F. Comellas, J. Ozon, and J.G. Peters. Deterministic Small-World Communication Networks. Information Processing Letters, 76:83--90, 2000.

  5. D. Coudert, A. Ferreira, and X. Muñoz. Topologies for Optical Interconnection Networks Based on the Optical Transpose Interconnection System. OSA Applied Optics -- Information Processing, 39(17):2965--2974, June 2000.

  6. D. Coudert, A. Ferreira, and X. Muñoz. A Multihop-Multi-OPS Optical Interconnection Network. IEEE/OSA Journal of Lightwave Technology, 18(12):2076--2085, 2000.

  7. Q. Gu and H. Tamaki. Multicolor routing in the undirected hypercube. Discrete Applied Mathematics, 100:169-181, 2000.

  8. L. Stacho and I. Vrtó. Virtual path layouts in ATM networks. SIAM J. Computing, 29:1621--1629, 2000.

  9. Shmuel Zaks. On the Use of Duality and Geometry in Layouts for ATM Networks.. In MFCS, pages 114-131, 2000. [PDF ]

1999
  1. B. Beauquier. All-to-All Communication in some Wavelength-Routed All-Optical Networks. Networks, 33(3):179--187, May 1999.

  2. Q. Gu and S. Peng. Unicast in hypercubes with large number of faulty nodes. IEEE Trans. on Parallel and Distributed Systems, 10(10):964-975, 1999.

  3. C. Laforest, A. L. Liestman, D. Peleg, T. Shermer, and D. Sotteau. Edge Disjoint Spanners of Complete Graphs and Complete Digraphs. Discr. Math., 203:133-159, 1999.

  4. B. Beauquier, S. Pérennes, and D. Tóth. All-to-All Routing and Coloring in Weighted Trees of Rings. In Proc. of 11th ACM Symposium on Parallel Algorithms and Architectures (SPAA'99), Saint-Malo, France, pages 185--190, June 1999. ACM Press.

  5. P. Berenbrink and C. Scheideler. Locally Efficient On-Line Strategies for Routing Packets along Fixed Paths. In Proceedings of the 10th ACM SIAM Symposium on Discrete Algorithms (SODA), pages 112-121, 1999.

  6. J. Manuch and L. Stacho. Fault-tolerant wavelength allocations in all-optical hypercubes. In International Colloquium on Structural Information and Communication Complexity -- SIROCCO, Ottawa, Canada, pages 219--232, June 1999. Carleton Scientific.

1998
  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.

  3. L. Stacho and I. Vrtó. Bisection width of transposition graphs and its applications. Discrete Applied Mathematics, 84:221--235, 1998.

1997
  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.

1996
  1. M.-C. Heydemann, J.G. Peters, and D. Sotteau. Spanners of Hypercube-Derived Networks. SIAM Journal on Discrete Mathematics, 9(1):37--54, 1996.

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

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

1994
  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.

1993
  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.

1992
  1. 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.

  2. J.-C. Bermond, P. Hell, A.L. Liestman, and J.G. Peters. Sparse broadcast graphs. Disc. Appl. Math., 36:97--130, 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.

1991
  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.

1990
  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. Existence of resolvable path designs. European J. Combin., 11(3):205--211, 1990.

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

no year
  1. J.-C. Bermond, R. Correa, and M.-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Discrete Mathematics year= 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. E. Chavez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Traversal of a quasi-planar subdivision without using mark bits. Journal of Interconnection Networks, to appear.

  3. D. Kral and L. Stacho. Closure for the property of having hamiltonian prism. Journal of Graph Theory, to appear.

  4. F. Comellas and P. Hell. Broadcasting in generalized chordal rings.
    Note: Accepted to Networks.

  5. C. Garcia, P. Hell, and C. Peyrat. Broadcasting in one orthant.
    Note: Submitted to Discrete Math..

  6. L. Gargano, P. Hell, L. Stacho, and U. Vaccaro. Spanning spiders in graphs and switches that split light.
    Note: Submitted.



Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.



Last modified: Tue Jun 10 22:49:14 2014
Author: dcoudert.

This document was translated from BibTEX by bibtex2html