Publications of year 2000

1. A. Ferreira and G. Kindervater, editors. Parallel Computing -- Special Issue on High Performance Computing in Operations Research, volume 26. Elsevier Science B. V., 2000.
   

   @BOOK{FeKi00,
   EDITOR = {A. Ferreira and G. Kindervater},
   NUMBER = {1},
   PUBLISHER = {Elsevier Science B. V.},
   TITLE = {Parallel Computing -- Special Issue on High Performance Computing in Operations Research},
   VOLUME = {26},
   YEAR = {2000},
   
   }
   

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

   @PhdThesis{Bea00,
   author = "B. Beauquier",
   title = "Communications dans les réseaux optiques par multiplexage en longueur d'onde",
   school = "université de Nice-Sophia Antipolis -- STIC",
   year = "2000",
   month = "janvier",
   POSTSCRIPT = "ftp://ftp-sop.inria.fr/mascotte/Publications/Bea00.ps.gz",
   
   }
   



2. T. Jiménez. Simulation de trafic routier: Étude des méthodologies de modélisation et parallélisation et mise en oe uvre. PhD thesis, université de Nice-Sophia Antipolis, September 2000.
   

   @PHDTHESIS{Jim00,
   AUTHOR = {T. Jiménez},
   MONTH = sep,
   SCHOOL = {université de Nice-Sophia Antipolis},
   TITLE = {Simulation de trafic routier: Étude des méthodologies de modélisation et parallélisation et mise en \oe uvre},
   YEAR = {2000} 
   }
   



3. N. Marlin. Communications Structurées dans les Réseaux. PhD thesis, université de Nice-Sophia Antipolis, juin 2000.
   

   @PhdThesis{Mar00,
   author = {N. Marlin},
   title = {Communications Structurées dans les Réseaux},
   school = {université de Nice-Sophia Antipolis},
   year = {2000},
   address = {},
   month = {juin},
   
   
   
   }
   

1. E. Altman, E. Baçsar, T. Jiménez, and N. Shimkin. Routing into Two Parallel Links:Game-Theoretic Distributed Algorithms. Journal of Parallel and Distributed Computing, (Special Issue on Routing in Computer and Communication Networks), 2000.
   

   @ARTICLE{ABJ+00b,
   AUTHOR="E. Altman and E. Ba{\c c}sar and T. Jiménez and N. Shimkin",
   TITLE="Routing into Two Parallel Links:Game-Theoretic Distributed Algorithms",
   JOURNAL="Journal of Parallel and Distributed Computing",
   NUMBER="Special Issue on Routing in Computer and Communication Networks",
   YEAR="2000" 
   }
   



2. E. Altman, T. Jiménez, and G. Koole. On optimal call admission control. IEEE Trans. on Communications, 2000.
   

   @ARTICLE{AJK00,
   AUTHOR="E. Altman and T. Jiménez and G. Koole",
   TITLE="On optimal call admission control",
   JOURNAL="IEEE Trans. on Communications",
   YEAR="2000" 
   }
   



3. M. Becker, A.-L. Beylot, O. Dalle, R. Dhaou, M. Marot, P. Mussi, C. Rigal, and V. Sutter. The ASIMUT Simulation Workshop. Networking and Information Systems Journal, 3(2):335--348, 2000.
   

   @article{BBDD+00,
   AUTHOR = {Becker, M. and Beylot, A.-L. and Dalle, O. and Dhaou, R. and Marot, M. and Mussi, P. and Rigal, C. and Sutter, V.},
   TITLE = {The ASIMUT Simulation Workshop},
   JOURNAL = {Networking and Information Systems Journal},
   YEAR = 2000,
   VOLUME = 3,
   NUMBER = 2,
   pages = {335--348} 
   }
   



4. C. Berge and B. Reed. Optimal packings of edge-disjoint odd cycles. Discrete Math., 211(1-3):197--202, 2000.
   

   @article {MR1735345,
   AUTHOR = {Berge, C. and Reed, B.},
   TITLE = {Optimal packings of edge-disjoint odd cycles},
   JOURNAL = {Discrete Math.},
   VOLUME = {211},
   YEAR = {2000},
   NUMBER = {1-3},
   PAGES = {197--202},
   
   }
   



5. J.-C. Bermond, J. Bond, C. Martin, A. Pekec, and F. S. Roberts. Optimal orientation of annular networks. JOIN, 1(1):21-46, 2000. [PDF ]
   

   @Article{BBM+00,
   Author= {J.-C. Bermond and J. Bond and C. Martin and A. Pekec and F. S. Roberts},
   Title= {Optimal orientation of annular networks},
   Year={2000},
   Journal={ JOIN },
   Volume= {1},
   Number= {1},
   Pages= {21-46},
   PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BBM+00.pdf},
   
   }
   



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

   @article{BGPR+00,
   author= { J.-C. Bermond and L. Gargano and S. P\'erennes and A.A. Rescigno and U. Vaccaro },
   title= { Efficient Collective Communications in Optical Networks },
   journal= { Theoretical Computer Science },
   year= { 2000 },
   volume= { 233 },
   number = {1-2},
   pages= { 165--189 },
   pdf= { ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BGP+00.pdf },
   
   }
   



7. J.-C. Bermond, S. Marshall, and M.L. Yu. Improved bounds for gossiping in mesh-bus networks. JOIN, 1(1):1-19, 2000. [PDF ]
   

   @Article{BMY00,
   Author= {J.-C. Bermond and S. Marshall and M.L. Yu},
   Title={Improved bounds for gossiping in mesh-bus networks},
   Year={2000},
   Journal={ JOIN},
   Volume= {1},
   Number= {1},
   Pages= {1-19},
   PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BMY00.pdf},
   
   }
   



8. P. Berthomé, A. Ferreira, S. Pérennes, G. Plaxton, and B. Maggs. Sorting-based selection algorithms on hypercubic networks. Algorithmica, 26(2):237--254, 2000.
   

   @article{BFMP+00,
   author= { P. Berthom\'e and A. Ferreira and S. P\'erennes and G. Plaxton and B. Maggs },
   journal= { Algorithmica },
   pages= { 237--254 },
   title= { Sorting-based selection algorithms on hypercubic networks },
   volume= { 26 },
   number = {2},
   year= { 2000 },
   
   }
   



9. M. Bugliesi, G. Delzanno, L. Liquori, and M. Martelli. Object Calculi in Linear Logic. Journal of Logic and Computation, 10(1):75--104, 2000. [POSTSCRIPT ]
   

   @Article{BDLM00,
   author = {M. Bugliesi and G. Delzanno and L. Liquori and M. Martelli},
   title = {Object {C}alculi in {L}inear {L}ogic},
   journal = jlc,
   year = {2000},
   pages = {75--104},
   number = {1},
   volume = {10},
   editor = {Oxford University Press},
   POSTSCRIPT = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/jlc-00.ps.gz} 
   }
   



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

    Abstract:

    In this paper we study the design of regular multicast networks implemented with Optical Passive Star (OPS) couplers. We focus on an architecture based on both Kautz graphs and stack-graphs, and show that it is very cost-effective with respect to its resources requirements, namely the number of OPS couplers, power budget, scalability and number of transceivers, and presents a large ratio number-of-nodes/diameter. The important issue of medium access control is also addressed and control protocols for accessing the optical couplers are given and analyzed. Finally, we show through simulation that these control protocols efficiently implement shortest path routing on these networks.

    
    

    @ARTICLE{CFM00b,
    author = {D. Coudert and A. Ferreira and X. Mu{\~n}oz},
    title = {A Multihop-Multi-OPS Optical Interconnection Network},
    journal = {IEEE/OSA Journal of Lightwave Technology},
    year = {2000},
    volume = {18},
    pages = {2076-2085},
    number = {12},
    abstract = { In this paper we study the design of regular multicast networks implemented with Optical Passive Star (OPS) couplers. We focus on an architecture based on both Kautz graphs and stack-graphs, and show that it is very cost-effective with respect to its resources requirements, namely the number of OPS couplers, power budget, scalability and number of transceivers, and presents a large ratio number-of-nodes/diameter. The important issue of medium access control is also addressed and control protocols for accessing the optical couplers are given and analyzed. Finally, we show through simulation that these control protocols efficiently implement shortest path routing on these networks.},
    key = {December},
    postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFM-JLT00.ps.gz} 
    }
    



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

    Abstract:

    Many results exist in the literature describing technological and theoretical advances in optical network topologies and design. However, an essential effort has yet to be done in linking those results together. In this paper, we propose a step in this direction, by giving optical layouts for several graph-theoretical topologies studied in the literature, using the Optical Transpose Interconnection System (OTIS) architecture. These topologies include the family of Partitioned Optical Passive Star (POPS) and stack-Kautz networks as well as a generalization of the Kautz and de Bruijn digraphs.

    
    

    @ARTICLE{CFM00,
    author = {D. Coudert and A. Ferreira and X. Muñoz},
    title = {{Topologies for Optical Interconnection Networks Based on the Optical Transpose Interconnection System}},
    journal = {OSA Applied Optics -- Information Processing},
    year = {2000},
    volume = {39},
    pages = {2965-2974},
    number = {17},
    month = jun,
    abstract = {Many results exist in the literature describing technological and theoretical advances in optical network topologies and design. However, an essential effort has yet to be done in linking those results together. In this paper, we propose a step in this direction, by giving optical layouts for several graph-theoretical topologies studied in the literature, using the Optical Transpose Interconnection System (OTIS) architecture. These topologies include the family of Partitioned Optical Passive Star (POPS) and stack-Kautz networks as well as a generalization of the Kautz and de Bruijn digraphs.},
    postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFM-AO00.ps.gz} 
    }
    



12. A. Ferreira, A. Goldman, and S. W. Song. Broadcasting in bus interconnection networks. Journal of Interconnection Networks - JOIN, 1(2):73--94, 2000.
    

    @ARTICLE{FGS00,
    AUTHOR = {A. Ferreira and A. Goldman and S. W. Song},
    JOURNAL = {Journal of Interconnection Networks - JOIN},
    TITLE = {Broadcasting in bus interconnection networks},
    VOLUME = {1},
    NUMBER = {2},
    PAGES = {73--94},
    YEAR = {2000},
    
    }
    



13. A. Ferreira and Nicolas Schabanel. A randomized BSP/CGM algorithm for the maximal independent set. Parallel Processing Letters, 9(3):411--422, 2000.
    

    @ARTICLE{FeSc00,
    AUTHOR = {A. Ferreira and Nicolas Schabanel},
    ADDRESS = {Australia},
    JOURNAL = {Parallel Processing Letters},
    NUMBER = {3},
    PAGES = {411--422},
    TITLE = {A randomized {BSP/CGM} algorithm for the maximal independent set},
    VOLUME = {9},
    YEAR = {2000},
    
    }
    



14. J. Galtier. Load Balancing Issues in the Prepartitioning Method. Computers and Artificial Intelligence, 19(4), 2000. [PDF ]
    

    @Article{Gal00b,
    author = {J. Galtier},
    title = {Load Balancing Issues in the Prepartitioning Method},
    journal = {Computers and Artificial Intelligence},
    year = {2000},
    volume = {19},
    number = {4},
    pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal00b.pdf},
    
    }
    



15. C. McDiarmid and B. Reed. Channel assignment and weighted coloring. Networks, 36(2):114--117, 2000.
    

    @article {MR1793319,
    AUTHOR = {McDiarmid, C. and Reed, B.},
    TITLE = {Channel assignment and weighted coloring},
    JOURNAL = {Networks},
    VOLUME = {36},
    YEAR = {2000},
    NUMBER = {2},
    PAGES = {114--117},
    
    }
    



16. L. Perkovic and B. Reed. An improved algorithm for finding tree decompositions of small width. Internat. J. Found. Comput. Sci., 11(3):365--371, 2000.
    Note: Selected papers from the Workshop on Theoretical Aspects of Computer Science (WG 99), Part 1 (Ascona).
    

    @article {MR1792120,
    AUTHOR = {Perkovi{\'c}, L. and Reed, B.},
    TITLE = {An improved algorithm for finding tree decompositions of small width},
    NOTE = {Selected papers from the Workshop on Theoretical Aspects of Computer Science (WG 99), Part 1 (Ascona)},
    JOURNAL = {Internat. J. Found. Comput. Sci.},
    VOLUME = {11},
    YEAR = {2000},
    NUMBER = {3},
    PAGES = {365--371},
    
    }
    



17. B. Reed and R. Thomas. Clique minors in graphs and their complements. J. Combin. Theory Ser. B, 78(1):81--85, 2000.
    

    @article {MR1737626,
    AUTHOR = {Reed, B. and Thomas, R.},
    TITLE = {Clique minors in graphs and their complements},
    JOURNAL = {J. Combin. Theory Ser. B},
    VOLUME = {78},
    YEAR = {2000},
    NUMBER = {1},
    PAGES = {81--85},
    
    }
    

1. E. Altman, E. Baçsar, T. Jiménez, and N. Shimkin. Competitive Routing in Networks with Polynomial Cost. In IEEE Infocom 2000, pages 1586--1593, mars 2000.
   

   @INPROCEEDINGS{ABJ+00a,
   AUTHOR="E. Altman and E. Ba\c{c}sar and T. Jiménez and N. Shimkin",
   TITLE="Competitive Routing in Networks with Polynomial Cost",
   BOOKTITLE="IEEE Infocom 2000",
   MONTH="mars ",
   PAGES="1586--1593",
   YEAR="2000" 
   }
   



2. A. Andreev, A. Clementi, P. Penna, and J. Rolim. Parallel Read Operations Without Memory Contention. In Electronic Colloquium on Computational Complexity, volume TR00-53, 2000.
   

   @INPROCEEDINGS{ACPR00,
   author = "A. Andreev and A. Clementi and P. Penna and J. Rolim",
   title = "Parallel Read Operations Without Memory Contention",
   booktitle = "Electronic Colloquium on Computational Complexity",
   volume = "TR00-53",
   year = "2000" 
   }
   



3. B. Beauquier, K.S. Candan, A. Ferreira, S. Pérennes, and A. Sen. On shortest path problems with ``non-Markovian'' link contribution to path lengths. In Proc. of IFIP/TC6 Networking 2000 Conference, Paris, France, mai 2000.
   

   @InProceedings{BCF+00,
   author = {B. Beauquier and K.S. Candan and A. Ferreira and S. Pérennes and A. Sen},
   title = "On shortest path problems with ``non-{M}arkovian'' link contribution to path lengths",
   booktitle = {Proc. of IFIP/TC6 Networking 2000 Conference},
   OPTpages = {},
   year = {2000},
   address = {Paris, France},
   month = "mai",
   
   }
   



4. B. Beauquier and E. Darrot. Arbitrary size Waksman networks and their vulnerability. In Actes des $1^{res}$ Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'99), 2000. World Scientific.
   

   @InProceedings{BeDa00,
   author = {B. Beauquier and E. Darrot},
   title = "Arbitrary size {W}aksman networks and their vulnerability",
   year = {2000},
   OPTpages = {},
   publisher = {World Scientific},
   booktitle = {Actes des $1^{res}$ Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'99)},
   
   }
   



5. P. Bergé, A. Ferreira, J. Galtier, and S. Petit. A probabilistic study of inter-satellite links load in polar orbit satellite constellations. In $2^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2000), La Rochelle, France, pages 137--142, Mai 2000.
   

   @InProceedings{BFGP00a,
   author = {P. Bergé and A. Ferreira and J. Galtier and S. Petit},
   title = {A probabilistic study of inter-satellite links load in polar orbit satellite constellations},
   booktitle = {$2^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2000)},
   pages = {137--142},
   year = {2000},
   address = {La Rochelle, France},
   month = {Mai} 
   }
   



6. J.-C. Bermond, A. Bonnecaze, T. Kodate, S. Perennes, and P. Sole. Broadcasting in hypercubes in the circuit switched model. In Proc. Conference IPDPS 2000, Cancun, Mexico,, May 2000, pages 21-26, 2000. [PDF ]
   

   @InProceedings{BBK+00,
   Author= {J.-C. Bermond and A. Bonnecaze and T. Kodate and S. Perennes and P. Sole },
   Title= {Broadcasting in hypercubes in the circuit switched model},
   Year={2000},
   BookTitle={Proc. Conference IPDPS 2000, Cancun, Mexico,, May 2000},
   Pages={21-26},
   PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BBK+00.pdf},
   
   }
   



7. J-C. Bermond, L. Chacon, D. Coudert, and F. Tillerot. Conception d'un réseau WDM protégé par sous-réseaux. In 2ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'00), La Rochelle, France, pages 83-88, May 2000. INRIA. [WWW ] [PDF ]

   Abstract:

   Nous proposons une modélisation de la construction d'un réseau WDM protégé comme l'extension du problème classique de couverture des arêtes d'un graphe. Un ensemble de résultats est donné pour la réalisation de l'instance All-to-All sur un réseau en anneau.

   
   

   @INPROCEEDINGS{BC+00,
   author = {J-C. Bermond and L. Chacon and D. Coudert and F. Tillerot},
   title = {Conception d'un r\'eseau {WDM} prot\'eg\'e par sous-r\'eseaux},
   booktitle = {2\`eme Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'00)},
   year = {2000},
   pages = {83-88},
   address = {La Rochelle, France},
   month = May,
   abstract = {Nous proposons une modélisation de la construction d'un réseau WDM protégé comme l'extension du problème classique de couverture des arêtes d'un graphe. Un ensemble de résultats est donné pour la réalisation de l'instance All-to-All sur un réseau en anneau.},
   pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BC+00.pdf},
   url = {http://hal.inria.fr/inria-00429292},
   isbn = {2-7261-1157-2},
   publisher = {INRIA},
   
   
   
   }
   



8. G. Bongiovanni, A. Clementi, and P. Penna. A Note on Parallel Read Operations on Large Public Databases. In Proc. of ARACNE-00, International Workshop on Approximation and Randomized Algorithms in Communication Networks, volume Carleton Scientific Press, pages 123--133, 2000.
   

   @INPROCEEDINGS{BCP00,
   author = "G. Bongiovanni and A. Clementi and P. Penna",
   title = "A Note on Parallel Read Operations on Large Public Databases",
   booktitle = "Proc. of ARACNE-00, International Workshop on Approximation and Randomized Algorithms in Communication Networks",
   volume = "Carleton Scientific Press",
   pages = "123--133",
   year = "2000" 
   }
   



9. A. Clementi, A. Ferreira, P. Penna, S. Pérennes, and R. Silvestri. The Minimum Range Assignment Problem on Linear Radio Networks. In Proc. of ESA-00, 8th Annual European Symposium on Algorithms, volume LNCS, pages 143--154, 2000.
   

   @INPROCEEDINGS{CFP+00,
   author = "A. Clementi and A. Ferreira and P. Penna and S. Pérennes and R. Silvestri",
   title = "The Minimum Range Assignment Problem on Linear Radio Networks",
   booktitle = "Proc. of ESA-00, 8th Annual European Symposium on Algorithms",
   year = "2000",
   volume = "LNCS",
   number = "1879",
   pages = "143--154" 
   }
   



10. A. Clementi, P. Penna, and R. Silvestri. On The Power Assignment Problem in Radio Networks. In Electronic Colloquium on Computational Complexity, volume TR00-54, 2000.
    

    @INPROCEEDINGS{CPS00b,
    author = "A. Clementi and P. Penna and R. Silvestri",
    title = "On The Power Assignment Problem in Radio Networks",
    booktitle = "Electronic Colloquium on Computational Complexity",
    volume = "TR00-54",
    year = "2000" 
    }
    



11. A. Clementi, P. Penna, and R. Silvestri. The Power Range Assignment Problem in Radio Networks on the Plane. In Proc. of STACS-00, 17th Annual Symposium on Theoretical Aspects of Computer Science, volume LNCS, pages 651--660, 2000.
    

    @INPROCEEDINGS{CPS00a,
    author = "A. Clementi and P. Penna and R. Silvestri",
    title = "The Power Range Assignment Problem in Radio Networks on the Plane",
    booktitle = "Proc. of STACS-00, 17th Annual Symposium on Theoretical Aspects of Computer Science",
    year = "2000",
    volume = "LNCS",
    number = "1770",
    pages = "651--660" 
    }
    



12. D. Colnet and L. Liquori. Match-O, a Statically Safe (?) Dialect of Eiffel. In TOOLS, International Conference on Technology of Object-Oriented Languages and Systems, pages 190--201, 2000. IEEE Computer Society. [POSTSCRIPT ]
    

    @INPROCEEDINGS{CoLi00b,
    AUTHOR = {Colnet, D. and Liquori, L.},
    TITLE = {Match-{O}, a {S}tatically {S}afe\,(?) {D}ialect of {E}iffel},
    YEAR = {2000},
    PUBLISHER = {IEEE Computer Society},
    BOOKTITLE = {TOOLS, International Conference on Technology of Object-Oriented Languages and Systems},
    PAGES = {190--201},
    POSTSCRIPT = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/tools-00.ps.gz} 
    }
    



13. D. Coudert, A. Ferreira, and S. Perennes. De Bruijn Isomorphisms and Free Space Optical Networks. In IEEE International Parallel and Distributed Processing Symposium, pages 769-774, 2000. IEEE Press. [PDF ] [POSTSCRIPT ]

    Abstract:

    The de Bruijn digraph $B(d,D)$ has degree $d$, diameter $D$, $d^D$ vertices and $d^{D+1}$ arcs. It is usually defined by words of size $D$ on an alphabet of cardinality $d$, through a cyclic left shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an {\em arbitrary} permutation on the alphabet {\bf and} an {\em arbitrary} permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is {\em cyclic}. We use this result to improve from $O\left(d^{D+1}\right)$ to $\Theta\left(\sqrt{d^{D+1}}\right)$ the number of lenses required for the implementation of $B(d,D)$ by the Optical Transpose Interconnection System proposed by Marsden {\em et al.} (Optics Letters 18(13):1083-1085, July 1993).

    
    

    @INPROCEEDINGS{CFP00,
    author = {D. Coudert and A. Ferreira and S. Perennes},
    title = {{De Bruijn Isomorphisms and Free Space Optical Networks}},
    booktitle = {IEEE International Parallel and Distributed Processing Symposium},
    year = {2000},
    pages = {769-774},
    publisher = {IEEE Press},
    abstract = {The de Bruijn digraph $B(d,D)$ has degree $d$, diameter $D$, $d^D$ vertices and $d^{D+1}$ arcs. It is usually defined by words of size $D$ on an alphabet of cardinality $d$, through a cyclic left shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an {\em arbitrary} permutation on the alphabet {\bf and} an {\em arbitrary} permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is {\em cyclic}. We use this result to improve from $O\left(d^{D+1}\right)$ to $\Theta\left(\sqrt{d^{D+1}}\right)$ the number of lenses required for the implementation of $B(d,D)$ by the Optical Transpose Interconnection System proposed by Marsden {\em et al.} (Optics Letters 18(13):1083-1085, July 1993).},
    pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFP-IPDPS00.pdf},
    postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFP-IPDPS00.ps.gz} 
    }
    



14. P. Crescenzi, G. Gambosi, and P. Penna. On-Line Algorithms for the Channel Assignment Problem in Cellular Networks. In Proc. of ACM DIALM-2000, 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pages 1--7, 2000.
    

    @INPROCEEDINGS{CGP00,
    author = "P. Crescenzi and G. Gambosi and P. Penna",
    title = "On-Line Algorithms for the Channel Assignment Problem in Cellular Networks",
    booktitle = "Proc. of ACM DIALM-2000, 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications",
    year = "2000",
    pages = "1--7" 
    }
    



15. O. Dalle, P. Mussi, and C. Rigal, and V. Sutter. ASIMUT: An Environment for the Simulation of Multi-Media Satellite Telecommunication Networks. In Proc. 6th ESA Workshop on Simulation in European Space Pragrams, ESTEC, Noordwijk, The Netherlands, pages 285--288, October 2000. European Space Agency. [WWW ]
    

    @InProceedings{DMRS00,
    Author= {O. Dalle and P. Mussi and and C. Rigal and V. Sutter},
    Title= {ASIMUT: An Environment for the Simulation of Multi-Media Satellite Telecommunication Networks},
    BookTitle={Proc. 6th ESA Workshop on Simulation in European Space Pragrams},
    Year={2000},
    Month={October},
    Organization={European Space Agency},
    ADDRESS = {ESTEC, Noordwijk, The Netherlands},
    url={http://www.inria.fr/mascotte/Olivier.Dalle/Postscript/ESA-SESP2000.ps.gz},
    pages={285--288},
    
    }
    



16. A. Ferreira, J. Galtier, P. Mahey, G. Mateus, and A. Oliveira. An Optimization Model for Routing in Low Earth Orbit Satellite Constellations. In Proceedings of ISPAN, Dallas, USA, December 2000.
    

    @INPROCEEDINGS{FGM+00,
    AUTHOR = {A. Ferreira and J. Galtier and P. Mahey and G. Mateus and A. Oliveira},
    ADDRESS = {Dallas, USA},
    BOOKTITLE = {Proceedings of ISPAN},
    MONTH = dec,
    TITLE = {An Optimization Model for Routing in Low Earth Orbit Satellite Constellations},
    YEAR = {2000},
    
    }
    



17. A. Ferreira, J. Galtier, and S. Pérennes. Approximation of a straight line in a bounded lattice. In $2^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2000), La Rochelle, France, pages 53--58, Mai 2000.
    

    @InProceedings{FGP00,
    author = {A. Ferreira and J. Galtier and S. P\'erennes},
    title = {Approximation of a straight line in a bounded lattice},
    booktitle = {$2^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2000)},
    pages = {53--58},
    year = {2000},
    address = {La Rochelle, France},
    month = {Mai} 
    }
    



18. P. Fraigniaud, A. Pelc, D. Peleg, and S. Pérennes. Assigning labels in unknown anonymous networks. In Proceedings of PODC 2000, (Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING), pages 101--112, 2000.
    

    @conference{FPPP00,
    title={Assigning labels in unknown anonymous networks},
    author={P. Fraigniaud and A. Pelc and D. Peleg and S. Pérennes},
    booktitle={Proceedings of PODC 2000, (Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING)},
    pages={101--112},
    year={2000},
    
    
    
    }
    



19. J. Galtier. Routing issues for LEO satellite constellations. In International Conference on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet (SSGRR 2000), L'Aquila, Italie, juillet 2000.
    

    @InProceedings{Gal00,
    author = {J. Galtier},
    title = {Routing issues for LEO satellite constellations},
    booktitle = {International Conference on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet (SSGRR 2000)},
    year = 2000,
    address = {L'Aquila, Italie},
    month = {juillet} 
    }
    



20. J. Galtier and S. Lanteri. On overlapping partitions. In David J. Lilja, editor, Proceedings of the 2000 International Conference on Parallel Processing, Toronto, Canada, pages 461--468, août 2000.
    

    @InProceedings{GaLa00,
    author = {J. Galtier and S. Lanteri},
    title = {On overlapping partitions},
    booktitle = {Proceedings of the 2000 International Conference on Parallel Processing},
    pages = {461--468},
    year = 2000,
    editor = {David J. Lilja},
    address = {Toronto, Canada},
    month = {août} 
    }
    



21. L. Gargano, A. Pelc, S. Pérennes, and U. Vaccaro. Efficient communication in unknown networks. In Proc. of WG'2000 - 26th International Workshop on Graph-Theoretic Concepts in Computer Science, 2000.
    Note: A paraître.
    

    @conference{GPPV00,
    author={L. Gargano and A. Pelc and S. Pérennes and U. Vaccaro},
    title={ Efficient communication in unknown networks},
    booktitle={ Proc. of WG'2000 - 26th International Workshop on Graph-Theoretic Concepts in Computer Science},
    year={2000},
    note={A paraître},
    
    }
    



22. S. Haddad, A. Laugier, and Jean-Francois Maurras. Designing telecommunication networks with global capacities under survivability constraints. In ECCO XIII, 2000.
    

    @InProceedings{HLM00a,
    AUTHOR = {S. Haddad and A. Laugier and Jean-Francois Maurras},
    TITLE = {Designing telecommunication networks with global capacities under survivability constraints},
    booktitle = {ECCO XIII},
    YEAR = {2000}
    }
    



23. S. Haddad, A. Laugier, and Jean-Francois Maurras. Global designing of telecommunication networks. In CO 2000, 2000.
    

    @InProceedings{HLM00b,
    AUTHOR = {S. Haddad and A. Laugier and Jean-Francois Maurras},
    TITLE = {Global designing of telecommunication networks},
    booktitle = {CO 2000},
    YEAR = {2000}
    }
    



24. M.-C. Heydemann, N. Marlin, and S. Pérennes. Rotational Cayley Graphs on Transposition Generated Groups (Extended Abstract). In 6ème Colloque International de Théorie des Graphes, Electronical Notes in Discrete Mathematics, pages 187--190, 2000. Elsevier Science.
    

    @InProceedings{HMP00b,
    author = {M.-C. Heydemann and N. Marlin and S. Pérennes},
    title = {Rotational Cayley Graphs on Transposition Generated Groups (Extended Abstract)},
    booktitle = {6ème Colloque International de Théorie des Graphes},
    pages = {187--190},
    year = {2000},
    series = {Electronical Notes in Discrete Mathematics},
    publisher = {Elsevier Science} 
    }
    



25. T. Jiménez. Optimal Admission Control for High Speed Networks: A Dynamic Programming Approach. In IEEE Conference on Decision and Control, decembre 2000.
    

    @INPROCEEDINGS{Jim00a,
    AUTHOR="T. Jiménez",
    TITLE="Optimal Admission Control for High Speed Networks: A Dynamic Programming Approach",
    BOOKTITLE="IEEE Conference on Decision and Control",
    MONTH="decembre",
    YEAR="2000" 
    }
    



26. T. Jiménez, P. Mussi, and G. Siegel. A road traffic simulator : car-following and lane-changing. In European Simulation Multiconference 2000, Gent, Belgium, pages 241--245, Mai 2000.
    

    @InProceedings{JMS00a,
    author = {T. Jiménez and P. Mussi and G. Siegel },
    title = {A road traffic simulator : car-following and lane-changing},
    booktitle = {European Simulation Multiconference 2000},
    ADDRESS = "Gent, Belgium",
    year = {2000},
    month = {Mai},
    pages={241--245},
    
    }
    



27. T. Jiménez, P. Mussi, and G. Siegel. The distribution and partitioning scheme of the HIPERTRANS traffic simulator. In European Simulation Symposium 2000, Hamburg, Allemagne, pages 462--466, September 2000.
    

    @InProceedings{JMS00b,
    author = {T. Jiménez and P. Mussi and G. Siegel },
    title = {The distribution and partitioning scheme of the {HIPERTRANS} traffic simulator},
    booktitle = {European Simulation Symposium 2000},
    ADDRESS = "Hamburg, Allemagne",
    year = {2000},
    month = {September},
    pages={462--466},
    
    }
    



28. A. Laugier and P. Mahey. Design of multi-level-protocol data networks. In $2^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2000), La Rochelle, France, pages 107--111, Mai 2000.
    

    @InProceedings{LaMa00,
    AUTHOR={A. Laugier and P. Mahey},
    TITLE={Design of multi-level-protocol data networks},
    booktitle = {$2^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2000)},
    pages = {107--111},
    year = {2000},
    address = {La Rochelle, France},
    month = {Mai} 
    
    
    }
    



29. M. Molloy and B. Reed. $k$-colouring when $k$ is close to $\Delta$. In 6th International Conference on Graph Theory (Marseille, 2000), volume 5 of Electron. Notes Discrete Math., Amsterdam, pages 4 pp. (electronic), 2000. Elsevier.
    

    @inproceedings{MR1969967,
    AUTHOR = {Molloy, M. and Reed, B.},
    TITLE = {{$k$}-colouring when {$k$} is close to {$\Delta$}},
    BOOKTITLE = {6th International Conference on Graph Theory (Marseille, 2000)},
    SERIES = {Electron. Notes Discrete Math.},
    VOLUME = {5},
    PAGES = {4 pp. (electronic)},
    PUBLISHER = {Elsevier},
    ADDRESS = {Amsterdam},
    YEAR = {2000},
    
    }
    



30. M. Molloy and B. Reed. Near-optimal list colorings. In Proceedings of the Ninth International Conference ``Random Structures and Algorithms'' (Poznan, 1999), volume 17, pages 376--402, 2000.
    

    @inproceedings {MR1801140,
    AUTHOR = {Molloy, M. and Reed, B.},
    TITLE = {Near-optimal list colorings},
    BOOKTITLE = {Proceedings of the Ninth International Conference ``Random Structures and Algorithms'' (Poznan, 1999)},
    JOURNAL = {Random Structures Algorithms},
    VOLUME = {17},
    YEAR = {2000},
    NUMBER = {3-4},
    PAGES = {376--402},
    
    }
    



31. P. Penna. Succinct Representations of Model Based Belief Revision. In Proc. of STACS-00, 17th Annual Symposium on Theoretical Aspects of Computer Science, volume LNCS, pages 205--216, 2000.
    

    @INPROCEEDINGS{Pen00,
    author = "P. Penna",
    title = "Succinct Representations of Model Based Belief Revision",
    booktitle = "Proc. of STACS-00, 17th Annual Symposium on Theoretical Aspects of Computer Science",
    year = "2000",
    volume = "LNCS",
    number = "1770",
    pages = "205--216" 
    }
    



32. B. Reed. How tall is a tree?. In Proceedings of the Thiry-Second Annual ACM Symposium on Theory of Computing, New York, pages 479--483 (electronic), 2000. ACM.
    

    @inproceedings {MR2115284,
    AUTHOR = {Reed, B.},
    TITLE = {How tall is a tree?},
    BOOKTITLE = {Proceedings of the Thiry-Second Annual ACM Symposium on Theory of Computing},
    PAGES = {479--483 (electronic)},
    PUBLISHER = {ACM},
    ADDRESS = {New York},
    YEAR = {2000},
    
    }
    

1. B. Beauquier, O. Delmas, and S. Pérennes. Tight bounds for broadcasting in the linear cost model. Rapport de Recherche 3827, INRIA, novembre 2000.
   

   @TechReport{BDP00,
   author = {B. Beauquier and O. Delmas and S. P\'erennes},
   title = "Tight bounds for broadcasting in the linear cost model",
   institution = {INRIA},
   year = {2000},
   type = {Rapport de Recherche},
   number = {3827},
   OPTaddress = {},
   month = "novembre",
   
   }
   



2. O. Dalle and C. Rigal. Exemple d'utilisation de l'environnement de simulation ASIMUT. Rapport technique ATF-SB-1-0043-CNES, C.N.E.S., Mars 2000.
   

   @techreport{DaRi00,
   AUTHOR = {Dalle, O. and Rigal, C.},
   TITLE = {Exemple d'utilisation de l'environnement de simulation {ASIMUT}},
   INSTITUTION = {C.N.E.S.},
   YEAR = {2000},
   MONTH = {Mars},
   TYPE = {Rapport technique},
   NUMBER = {ATF-SB-1-0043-CNES} 
   }
   



3. O. Dalle and V. Sutter. Spécification technique de besoin logiciel de l'environnement de simulation ASIMUT. Spécification ATF-SB-1-0029-CNES, C.N.E.S., Mars 2000.
   

   @techreport{DaSu00,
   AUTHOR = {Dalle, O. and Sutter, V.},
   TITLE = {Sp\'ecification technique de besoin logiciel de l'environnement de simulation {ASIMUT}},
   INSTITUTION = {C.N.E.S.},
   YEAR = {2000},
   MONTH = {Mars},
   TYPE = {Spécification},
   NUMBER = {ATF-SB-1-0029-CNES} 
   }
   



4. E. Darrot. Convention A11518 INRIA--Alcatel Space Industries. Rapport de contrat,version révisée, INRIA Sophia Antipolis, France, Mai 2000.
   

   @TechReport{Dar00,
   Author = {Darrot, E.},
   Title = {Convention A11518 {INRIA}--{A}lcatel {S}pace {I}ndustries},
   Type = {Rapport de contrat,version révisée},
   Institution = {INRIA Sophia Antipolis},
   Address = {France},
   Month = {Mai},
   Year = {2000} 
   }
   

1. F. Blanc. Problèmes de flips 3D. Rapport de stage, ESSI, 2000.
   

   @MastersThesis{Bla00,
   author = {F. Blanc},
   title = {Problèmes de flips 3D},
   school = {ESSI},
   year = {2000},
   type = {Rapport de stage},
   
   }
   



2. P. Boffa. L'internet dynamique. Rapport de stage de deuxième année, DUT Infocom IUT de Nice côte d'azur, Université de Nice Sophia-Antipolis, 2000.
   

   @MastersThesis{Bof00,
   author = {P. Boffa},
   title = {L'internet dynamique},
   school = {DUT Infocom IUT de Nice côte d'azur, Universit\'e de Nice Sophia-Antipolis},
   year = {2000},
   type = {Rapport de stage de deuxième année},
   
   }
   



3. B. Bongiovanni. IGP Interface Graphique pour PORTO. Rapport de DESS Telecoms, Université de Nice Sophia-Antipolis, 2000.
   

   @MastersThesis{Bon00,
   author = {B. Bongiovanni},
   title = {IGP Interface Graphique pour PORTO},
   school = {Universit\'e de Nice Sophia-Antipolis},
   year = {2000},
   type = {Rapport de DESS Telecoms},
   
   }
   



4. G. Conjat. Data Mining sur le Web avec applications à l'Analyse Technique des Marchés financiers. Rapport de stage, ESSI, 2000.
   

   @MastersThesis{Con00,
   author = {G. Conjat},
   title = {Data Mining sur le Web avec applications à l'Analyse Technique des Marchés financiers},
   school = {ESSI},
   type = {Rapport de stage},
   year = {2000},
   
   }
   



5. G.Huiban. Les problèmes de groupage dans les réseaux de télécommunication. Rapport de stage de deuxième année, ISIMA, Clermont-Ferrand, 2000.
   

   @MastersThesis{Hui00,
   author = {G.Huiban},
   title = {Les problèmes de groupage dans les réseaux de télécommunication},
   school = { ISIMA, Clermont-Ferrand},
   year = {2000},
   type = {Rapport de stage de deuxième année},
   
   }
   



6. J. Gavet. Hipertrans: validation et modification des algorithmes. Rapport de stage de deuxième année, ISIMA, Clermont-ferrand, 2000.
   

   @MastersThesis{Gav00,
   author = {J. Gavet},
   title = {Hipertrans: validation et modification des algorithmes},
   school = {ISIMA, Clermont-ferrand},
   year = {2000},
   type = {Rapport de stage de deuxième année},
   
   }
   



7. N. Lichiardopol. Points fixes des rotations complètes dans un graphe de cayley orienté. Rapport de DEA MDFI, Université de Luminy, Marseille, 2000.
   

   @MastersThesis{Lic00,
   author = {N. Lichiardopol},
   title = {Points fixes des rotations complètes dans un graphe de cayley orienté},
   school = {Universit\'e de Luminy, Marseille},
   year = {2000},
   type = {Rapport de DEA MDFI},
   
   }
   



8. F. Maginot. Réseaux tolérants aux pannes. Rapport de DEA MDFI, Université de Luminy, Marseille, 2000.
   

   @MastersThesis{Mag00,
   author = {F. Maginot},
   title = {Réseaux tolérants aux pannes},
   school = {Universit\'e de Luminy, Marseille},
   year = {2000},
   type = {Rapport de DEA MDFI},
   
   }
   



9. G. Masson. IGP Interface Graphique pour PORTO. Rapport de DESS Telecoms, Université de Nice Sophia-Antipolis, 2000.
   

   @MastersThesis{Mas00,
   author = {G. Masson},
   title = {IGP Interface Graphique pour PORTO},
   school = {Universit\'e de Nice Sophia-Antipolis},
   year = {2000},
   type = {Rapport de DESS Telecoms},
   
   }
   



10. J. Plouchart. Propositions méthodologiques pour la simulation multi-niveaux. Rapport de DEA RSD, Université de Nice Sophia-Antipolis, 2000.
    

    @MastersThesis{Plo00,
    author = {J. Plouchart},
    title = {Propositions méthodologiques pour la simulation multi-niveaux},
    school = {Université de Nice Sophia-Antipolis},
    year = {2000},
    type = {Rapport de DEA RSD},
    
    }
    



11. H. Rivano. La coloration fractionnaire appliquée à la résolution de problèmes de planification de réseaux optiques WDM. Rapport de DEA RSD, Université de Nice Sophia-Antipolis et ENS Lyon, 2000. [WWW ]
    

    @MASTERSTHESIS{Riv00,
    author = {H. Rivano},
    title = {La coloration fractionnaire appliquée à la résolution de problèmes de planification de réseaux optiques WDM},
    school = {Université de Nice Sophia-Antipolis et ENS Lyon},
    year = {2000},
    type = {Rapport de DEA RSD},
    url = {http://ensl.free.fr/rapports/} 
    }
    



12. B. Wack. Réseaux optiques à multiplexage en longueur d'onde. Rapport de stage de magistère d'informatique, ENS Lyon, 2000.
    

    @MastersThesis{Wac00,
    author = {B. Wack},
    title = {Réseaux optiques à multiplexage en longueur d'onde},
    school = {ENS Lyon},
    year = {2000},
    type = {Rapport de stage de magist\`ere d'informatique},
    
    }
    

This document was translated from BibT_EX by bibtex2html