Publications of year 2004

BACK TO COATI PUBLICATION INDEX

Publications of year 2004

Thesis
  1. J.-F. Lalande. Conception de réseaux de télécommunications : optimisation et expérimentations. PhD thesis, École doctorale STIC, Université de Nice-Sophia Antipolis, Décembre 2004. [PDF ] [POSTSCRIPT ]
    @phdthesis{Lal04,
    author = {J.-F. Lalande},
    title = {Conception de r\'eseaux de t\'el\'ecommunications~: optimisation et exp\'erimentations},
    year = {2004},
    month = {D\'ecembre},
    school = {\'Ecole doctorale STIC, Universit\'e de Nice-Sophia Antipolis},
    PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Francois.Lalande/articles/these_conception_de_reseaux_de_telecommunications_optimisation_et_experimentations.pdf},
    POSTSCRIPT={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Francois.Lalande/articles/these_conception_de_reseaux_de_telecommunications_optimisation_et_experimentations.ps.gz} 
    }
    

     
Articles in journal or book's chapters
  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. [PDF ]
    @article{BCLY04,
    author= {J-C. Bermond and C.J. Colbourn and A. Ling and M-L. Yu},
    title= {Grooming in unidirectional rings : $K_4 -e$ designs},
    journal= {Discrete Mathematics, Lindner's Volume},
    year= {2004},
    volume= {284},
    number= {1-3},
    pages= {57--62},
    PDF={http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BCLY04.pdf},
    
    }
    

     
  2. H.-J. Böckenhauer, D. Bongartz, J. Hromkovic, R. Klasing, G. Proietti, S. Seibert, and W. Unger. On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Theoretical Computer Science, 326(1--3):137--153, 2004.
    @Article{BBH+04,
    title = { On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality },
    author = { H.-J. B\"ockenhauer and D. Bongartz and J. Hromkovi\v{c} and R. Klasing and G. Proietti and S. Seibert and W. Unger },
    year = { 2004 },
    journal = { Theoretical Computer Science },
    pages = { 137--153 },
    volume = { 326 },
    number = { 1--3 },
    
    }
    

     
  3. I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, P. Persiano, and H. Rivano. Approximate Constrained Bipartite Edge Coloring. Discrete Applied Mathematics, 143(1-3):54--61, September 2004. [PDF ] [POSTSCRIPT ]
    Abstract:
    We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard event for bipartite graphs of maximum degree three.

    @article{CFKP+04,
    author= { I. Caragiannis and A. Ferreira and C. Kaklamanis and S. P\'erennes and P. Persiano and H. Rivano },
    title= { Approximate Constrained Bipartite Edge Coloring },
    journal= { Discrete Applied Mathematics },
    year= { 2004 },
    volume= { 143 },
    pages= { 54--61 },
    number= { 1-3 },
    month= { September },
    abstract= { We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard event for bipartite graphs of maximum degree three. },
    pdf= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/CFKP+04.pdf },
    postscript= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/CFKP+04.ps.gz },
    
    }
    

     
  4. M. Cosnard, E. Jeannot, and T. Yang. Compact Dag Representation and its Symbolic Scheduling. Journal of Parallel and Distributed Computing, 64(8):921--935, August 2004.
    @Article{CJY04,
    author = {M. Cosnard and E. Jeannot and T. Yang},
    title = "{Compact Dag Representation and its Symbolic Scheduling}",
    journal = "{Journal of Parallel and Distributed Computing}",
    year = {2004},
    volume = {64},
    number = {8},
    pages = {921--935},
    month = {August},
    
    }
    

     
  5. S. Céroi and F. Havet. Trees with three leaves are $(n+1)$-unavoidable. Discrete Applied Mathematics, 141:19--39, 2004. [PDF ]
    @ARTICLE{CeHa04,
    AUTHOR = "S. C\'eroi and F. Havet",
    TITLE = "Trees with three leaves are $(n+1)$-unavoidable",
    JOURNAL = "Discrete Applied Mathematics",
    VOLUME = "141",
    YEAR = "2004",
    PAGES = "19--39",
    PDF = "ftp://ftp-sop.inria.fr/mascotte/Publications/CeHa04.pdf",
    
    }
    

     
  6. S. Dantas, C. M. H. de Figueiredo, S. Klein, S. Gravier, and B. Reed. Stable skew partition problem. Discrete Appl. Math., 143(1-3):17--22, 2004.
    @article {MR2087864,
    AUTHOR = {Dantas, S. and de Figueiredo, C. M. H. and Klein, S. and Gravier, S. and Reed, B.},
    TITLE = {Stable skew partition problem},
    JOURNAL = {Discrete Appl. Math.},
    VOLUME = {143},
    YEAR = {2004},
    NUMBER = {1-3},
    PAGES = {17--22},
    
    }
    

     
  7. M. DeVos, G. Ding, B. Oporowski, D. P. Sanders, B. Reed, P. Seymour, and D. Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Combin. Theory Ser. B, 91(1):25--41, 2004.
    @article {MR2047529,
    AUTHOR = {DeVos, M. and Ding, G. and Oporowski, B. and Sanders, D. P. and Reed, B. and Seymour, P. and Vertigan, D.},
    TITLE = {Excluding any graph as a minor allows a low tree-width 2-coloring},
    JOURNAL = {J. Combin. Theory Ser. B},
    VOLUME = {91},
    YEAR = {2004},
    NUMBER = {1},
    PAGES = {25--41},
    
    }
    

     
  8. A. Ferreira. Building a reference combinatorial model for MANETs. IEEE Network, 18(5):24--29, 2004.
    @Article{Fer04,
    title={Building a reference combinatorial model for MANETs},
    author={A. Ferreira},
    journal={{IEEE} Network},
    volume={18},
    number={5},
    year={2004},
    pages={24--29},
    
    }
    

     
  9. G. Fertin, A. Raspaud, and B. Reed. Star coloring of graphs. J. Graph Theory, 47(3):163--182, 2004.
    @article {MR2089462,
    AUTHOR = {Fertin, G. and Raspaud, A. and Reed, B.},
    TITLE = {Star coloring of graphs},
    JOURNAL = {J. Graph Theory},
    VOLUME = {47},
    YEAR = {2004},
    NUMBER = {3},
    PAGES = {163--182},
    
    }
    

     
  10. M. Flammini and S. Pérennes. Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols. SIAM Journal on Discrete Mathematics, 17(4):521--540, 2004. [PDF ]
    @article{FlPe04,
    author= { M. Flammini and S. P\'erennes },
    title= { Lower Bounds on the Broadcasting and Gossiping Time of Restricted Protocols },
    journal= { SIAM Journal on Discrete Mathematics },
    volume= { 17 },
    number= { 4 },
    pages= { 521--540 },
    publisher= { SIAM, Philadelphia, USA },
    year= { 2004 },
    pdf= {ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/FlPe04.pdf },
    
    }
    

     
  11. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in Graphs. Journal of Algorithms, 53(1):85--112, 2004. [PDF ]
    @article{GPPR04,
    title= { Distance labeling in Graphs },
    author= { C. Gavoille and D. Peleg and S. P\'erennes and R. Raz },
    year= { 2004 },
    journal= { Journal of Algorithms },
    pages= { 85--112 },
    volume= { 53 },
    number = {1},
    pdf= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/GPPR04.pdf },
    
    }
    

     
  12. F. Havet. Stable set meeting every longest path. Discrete Mathematics, 289(1--3):169--173, 2004. [PDF ]
    @ARTICLE{Hav04b,
    AUTHOR = "F. Havet",
    TITLE = "Stable set meeting every longest path",
    JOURNAL = "Discrete Mathematics",
    VOLUME = "289",
    NUMBER = "1--3",
    YEAR = "2004",
    PAGES = "169--173",
    PDF = "ftp://ftp-sop.inria.fr/mascotte/Publications/Hav04b.pdf",
    
    }
    

     
  13. F. Havet and M. Wennink. The Push Tree Problem. Networks, 44(4):281--291, 2004. [PDF ]
    @ARTICLE{HaWe04,
    AUTHOR = "F. Havet and M. Wennink",
    TITLE = "The Push Tree Problem",
    JOURNAL = "Networks",
    VOLUME = "44",
    NUMBER = "4",
    YEAR = "2004",
    PAGES = "281--291",
    PDF = "ftp://ftp-sop.inria.fr/mascotte/Publications/HaWe04.pdf",
    
    }
    

     
  14. F. Havet. Pancyclic arcs and connectivity in tournaments. Journal of Graph Theory, 47(2):87--110, 2004. [PDF ]
    @ARTICLE{Hav04,
    AUTHOR = "F. Havet",
    TITLE = "Pancyclic arcs and connectivity in tournaments",
    JOURNAL = "Journal of Graph Theory",
    VOLUME = "47",
    NUMBER = "2",
    YEAR = "2004",
    PAGES = "87--110",
    PDF = "ftp://ftp-sop.inria.fr/mascotte/Publications/Hav04.pdf",
    
    }
    

     
  15. C. T. Hoàng and B. Reed. On the co-$P\sb 3$-structure of perfect graphs. SIAM J. Discrete Math., 18(3):571--576 (electronic), 2004/05.
    @article {MR2134417,
    AUTHOR = {Ho{\`a}ng, C. T. and Reed, B.},
    TITLE = {On the co-{$P\sb 3$}-structure of perfect graphs},
    JOURNAL = {SIAM J. Discrete Math.},
    VOLUME = {18},
    YEAR = {2004/05},
    NUMBER = {3},
    PAGES = {571--576 (electronic)},
    
    }
    

     
  16. R. Klasing and C. Laforest. Hardness results and approximation algorithms of $k$-tuple domination in graphs. Information Processing Letters, 89(2):75--83, 2004. [WWW ]
    @article{KlLa04,
    author = {R. Klasing and C. Laforest},
    title = {Hardness results and approximation algorithms of $k$-tuple domination in graphs},
    journal = {Information Processing Letters},
    volume = {89},
    number = {2},
    year = {2004},
    issn = {0020-0190},
    pages = {75--83},
    URL = {http://dx.doi.org/10.1016/j.ipl.2003.10.004},
    publisher = {Elsevier North-Holland, Inc.},
    
    }
    

     
  17. B. Reed and P. Seymour. Hadwiger's conjecture for line graphs. European J. Combin., 25(6):873--876, 2004.
    @article {MR2079904,
    AUTHOR = {Reed, B. and Seymour, P.},
    TITLE = {Hadwiger's conjecture for line graphs},
    JOURNAL = {European J. Combin.},
    VOLUME = {25},
    YEAR = {2004},
    NUMBER = {6},
    PAGES = {873--876},
    
    }
    

     
  18. B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299--301, 2004.
    @article {MR2057781,
    AUTHOR = {Reed, B. and Smith, K. and Vetta, A.},
    TITLE = {Finding odd cycle transversals},
    JOURNAL = {Oper. Res. Lett.},
    VOLUME = {32},
    YEAR = {2004},
    NUMBER = {4},
    PAGES = {299--301},
    
    }
    

     
  19. B. Reed, S. W. Song, and J. L. Szwarcfiter. Preface [Brazilian Symposium on Graphs, Algorithms and Combinatorics]. Discrete Appl. Math., 141(1-3):1, 2004.
    Note: Held in Fortaleza, 2001.
    @article {MR2065894,
    AUTHOR = {Reed, B. and Song, S. W. and Szwarcfiter, J. L.},
    TITLE = {Preface [{B}razilian {S}ymposium on {G}raphs, {A}lgorithms and {C}ombinatorics]},
    NOTE = {Held in Fortaleza, 2001},
    JOURNAL = {Discrete Appl. Math.},
    VOLUME = {141},
    YEAR = {2004},
    NUMBER = {1-3},
    PAGES = {1},
    
    }
    

     
Conference's articles
  1. S. Bessy and S. Thomassé. Three min-max theorems concerning cyclic orders of strong digraphs. In Acts of IPCO X 2004, volume 3064 of Lecture Notes in Computer Sciences, pages 132--138, 2004. Springer-Verlag. [WWW ]
    @inProceedings{BeTh04,
    AUTHOR = {Bessy, S. and Thomass\'e, S.},
    TITLE = {Three min-max theorems concerning cyclic orders of strong digraphs},
    booktitle= {Acts of IPCO X 2004},
    series= {Lecture Notes in Computer Sciences},
    volume = {3064},
    pages={132--138},
    PUBLISHER = {Springer-Verlag},
    YEAR = {2004},
    URL ={http://lapcs.univ-lyon1.fr/~bessy/},
    
    }
    

     
  2. S. Bessy. Un algorithme d'approximation pour le sous-digraphe fortement connexe minimal. In Sixièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'04), pages 57--61, 2004. INRIA. [WWW ]
    @inProceedings{Bes04,
    AUTHOR = {Bessy, S.},
    TITLE = {Un algorithme d'approximation pour le sous-digraphe fortement connexe minimal},
    booktitle = {Sixi\`emes Rencontres Francophones sur les Aspects Algorithmiques des T\'el\'ecommunications (AlgoTel'04)},
    YEAR = {2004},
    pages = {57--61},
    PUBLISHER = {INRIA},
    URL ={http://ares.insa-lyon.fr/algotel2004/program.shtml},
    
    }
    

     
  3. C. Cooper, R. Klasing, and M. Zito. Dominating Sets in Web Graphs. In Proceedings of the Third Workshop on Algorithms and Models for the Web-Graph (WAW 2004), volume 3243 of Lecture Notes in Computer Science, pages 31--43, October 2004. Springer-Verlag.
    @conference{CKZ04,
    author= {C. Cooper and R. Klasing and M. Zito},
    title= {Dominating Sets in Web Graphs},
    booktitle= {Proceedings of the Third Workshop on Algorithms and Models for the Web-Graph (WAW 2004)},
    series= {Lecture Notes in Computer Science},
    publisher= {Springer-Verlag},
    volume={3243},
    pages={31--43},
    year= {2004},
    month={October},
    
    }
    

     
  4. A. Ferreira and A. Jarry. Complexity of Minimum Spanning Tree in Evolving Graphs and the Minimum-Energy Broadcast Routing Problem. In Proceedings of WiOpt'04 -- Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks, Cambridge, United Kingdom, March 2004.
    @InProceedings{FeJa04,
    author={A. Ferreira and A. Jarry},
    title={Complexity of Minimum Spanning Tree in Evolving Graphs and the Minimum-Energy Broadcast Routing Problem},
    booktitle ={Proceedings of WiOpt'04 -- Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks},
    year = {2004},
    address = {Cambridge, United Kingdom},
    month = {March},
    
    }
    

     
  5. M. Flammini, R. Klasing, A. Navarra, and S. Pérennes. Improved approximation results for the Minimum Energy Broadcasting Problem. In 2nd ACM/SIGMOBILE Annual International Joint Workshop on Foundation of Mobile Computing (DIALM-POMC 2004), pages 85--91, 2004. ACM Press. [WWW ] [POSTSCRIPT ]
    @inproceedings{FKNP04,
    title= { Improved approximation results for the Minimum Energy Broadcasting Problem },
    author= { M. Flammini and R. Klasing and A. Navarra and S. P\'erennes },
    pages = {85--91},
    URL= {http://doi.acm.org/10.1145/1022630.1022644},
    publisher = {ACM Press},
    isbn = {1-58113-921-7},
    booktitle= { 2nd ACM/SIGMOBILE Annual International Joint Workshop on Foundation of Mobile Computing (DIALM-POMC 2004) },
    year= { 2004 },
    POSTSCRIPT= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/FKNP04.ps },
    
    }
    

     
  6. S. Funke, A. Kesselman, Z. Lotker, and M. Segal. Improved Algorithms for the Connected Sensor Cover Problem. In ADHOC-NOW 04, pages 56--59, 2004.
    @InProceedings{FKLS04,
    title={Improved Algorithms for the Connected Sensor Cover Problem},
    author={S. Funke and A. Kesselman and Z. Lotker and M. Segal},
    booktitle={ADHOC-NOW 04},
    pages={56--59},
    year={2004},
    
    }
    

     
  7. J. Galtier. Optimizing the IEEE 802.11b Performance using Slow Congestion Window Decrease. In Proccedings of the 16th ITC Specialist Seminar on performance evaluation of wireless and mobile systems, Antwerpen, Belgium, pages 165--176, August/September 2004. [PDF ]
    @InProceedings{Gal04a,
    author ={J. Galtier},
    title ={Optimizing the {IEEE} 802.11b Performance using Slow Congestion Window Decrease},
    booktitle ={Proccedings of the 16th ITC Specialist Seminar on performance evaluation of wireless and mobile systems},
    pages = {165--176},
    year = {2004},
    address = {Antwerpen, Belgium},
    month = {August/September},
    pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal04a.pdf},
    
    }
    

     
  8. C. Gomes and G. Robson Mateus. Routing and Wavelength Assignment in a Mesh Network. In 3rd International Information and Telecommunication Technologies Symposium (I2TS), 2004.
    @INPROCEEDINGS{GM04,
    AUTHOR = {C. Gomes and G. {Robson Mateus}},
    TITLE = {Routing and Wavelength Assignment in a Mesh Network},
    BOOKTITLE = {3rd International Information and Telecommunication Technologies Symposium (I2TS)},
    SCHOOL = {S\~ao Carlos Federal University (UFSCar), SP},
    YEAR = {2004},
    
    }
    

     
  9. A. Jarry and A. Laugier. On the minimum number edges of two-connected graphs with given diameter. In GT04, Paris, France, July 2004.
    @InProceedings{JaLa04,
    author = {A. Jarry and A. Laugier},
    title = {On the minimum number edges of two-connected graphs with given diameter},
    booktitle = {GT04},
    year = {2004},
    address = {Paris, France},
    month = {July},
    
    }
    

     
  10. A. Jarry and Z. Lotker. Connectivity in Evolving Graph with Geometric Properties. In Dial MPOMC 2004 The Second ACM/SIGMOBILE Annual International Joint Workshop on Foundations of Mobile Computing, 2004.
    @conference{JaLo04,
    title= {Connectivity in Evolving Graph with Geometric Properties},
    author= {A. Jarry and Z. Lotker},
    year= {2004},
    booktitle= {Dial MPOMC 2004 The Second ACM/SIGMOBILE Annual International Joint Workshop on Foundations of Mobile Computing},
    
    }
    

     
  11. A. Jarry. Integral Symmetric 2-Commodity Flows. In Proceedings of STACS'04, Montpellier, March 2004.
    @InProceedings{Jar04,
    author={A. Jarry},
    title = {Integral Symmetric 2-Commodity Flows},
    booktitle = {Proceedings of STACS'04},
    year = {2004},
    address = {Montpellier},
    month = {March},
    
    }
    

     
  12. R. Klasing, A. Navarra, A. Papadopoulos, and S. Pérennes. Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the Minimum Energy Broadcast Routing Problem. In Proc. 3rd FIP-TC6 Networking Conference ( Networking 2004), volume 3042 of Lecture Notes in Computer Science, pages 866--877, 2004. Springer-Verlag. [POSTSCRIPT ]
    @conference{KNPP04,
    author= { R. Klasing and A. Navarra and A. Papadopoulos and S. P\'erennes },
    title= { Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the Minimum Energy Broadcast Routing Problem },
    booktitle= { Proc.\ 3rd FIP-TC6 Networking Conference ( Networking~2004) },
    series={Lecture Notes in Computer Science},
    volume={3042},
    publisher={Springer-Verlag},
    pages= { 866--877 },
    year= { 2004 },
    POSTSCRIPT= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/KNPP04.ps },
    
    }
    

     
  13. G. Kozma, Z. Lotker, M. Sharir, and G. Stupp. Geometrically Aware Communication in Random Wireless Networks. In 24th ACM Symp. on Principles of Distributed Computing, pages 310--319, 2004.
    @InProceedings{KLSS04,
    title={Geometrically Aware Communication in Random Wireless Networks},
    author={G. Kozma and Z. Lotker and M. Sharir and G. Stupp},
    booktitle={24th ACM Symp.~on Principles of Distributed Computing},
    pages={310--319},
    year={2004},
    
    }
    

     
  14. L. Liquori and B. P. Serpette. iRho: an imperative rewriting calculus. In Proc. of ACM-PPDP: International Conference on Principles and Practice of Declarative Programming, pages 167--178, 2004. [POSTSCRIPT ]
    @inproceedings{LiSe04,
    author = {L. Liquori and B. P. Serpette},
    title = {iRho: an imperative rewriting calculus},
    booktitle = {Proc. of ACM-PPDP: International Conference on Principles and Practice of Declarative Programming},
    year = {2004},
    pages = {167--178},
    POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/ppdp-04.ps.gz} 
    }
    

     
  15. Z. Lotker, M. Martinez de Albeniz, and S. Pérennes. Range-Free Ranking in Sensors Networks and Its Applications to Localization. In ADHOC-NOW 2004, pages 158--171, 2004. [POSTSCRIPT ]
    @inproceedings{LMP04,
    title= {Range-Free Ranking in Sensors Networks and Its Applications to Localization},
    author= {Z. Lotker and Martinez de Albeniz, M. and S. P\'erennes},
    booktitle= {ADHOC-NOW 2004},
    pages= {158--171},
    year= {2004},
    postscript= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/ALP04.ps } 
    }
    

     
  16. J. Moulierac, J-C. König, and M. Molnár. Diffusion contrainte dans un groupe. In ALGOTEL - Rencontre francophone sur les aspects Algorithmiques des Télécommunications, 2004. [PDF ]
    Abstract:
    Dans ce papier nous traitons de problemes particuliers de communications de groupe dans les reseaux. Le probleme de diffusion contrainte dans un groupe consiste \`a envoyer un message d'un \'emetteur \`a un ensemble de destinataires en imposant son passage par des noeuds sp\'ecifiques appel\'es les traducteurs. Dans un premier temps, nous prouvons que ce probleme est NP-difficile et nous proposons une heuristique r-approchee pour le resoudre, ou r est le facteur d'approximation de l'heuristique pour le probleme de Steiner. Dans un deuxieme temps, nous presentons une heuristique permettant de resoudre le probeme de diffusion contrainte dans un groupe auquel on a rajoute une contrainte d'equilibrage.

    @inproceedings{MKM04,
    author = {J. Moulierac and J-C. K\"onig and M. Moln\'ar},
    title = {{Diffusion contrainte dans un groupe}},
    booktitle = {ALGOTEL - Rencontre francophone sur les aspects Algorithmiques des T\'el\'ecommunications},
    year = {2004},
    PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/moulierac04diffusion.pdf},
    ABSTRACT={Dans ce papier nous traitons de problemes particuliers de communications de groupe dans les reseaux. Le probleme de diffusion contrainte dans un groupe consiste \`a envoyer un message d'un \'emetteur \`a un ensemble de destinataires en imposant son passage par des noeuds sp\'ecifiques appel\'es les traducteurs. Dans un premier temps, nous prouvons que ce probleme est NP-difficile et nous proposons une heuristique r-approchee pour le resoudre, ou r est le facteur d'approximation de l'heuristique pour le probleme de Steiner. Dans un deuxieme temps, nous presentons une heuristique permettant de resoudre le probeme de diffusion contrainte dans un groupe auquel on a rajoute une contrainte d'equilibrage.} 
    }
    

     
Internal reports
  1. S. Alouf, E. Altman, J. Galtier, J.-F. Lalande, and C. Touati. Un algorithme d'allocation de bande passante satellitaire. Research Report RR-5172, INRIA Sophia Antipolis, 2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis, April 2004. [WWW ] [PDF ] [POSTSCRIPT ]
    @TechReport{AAG+04,
    author = {S. Alouf and E. Altman and J. Galtier and J.-F. Lalande and C. Touati},
    institution = {INRIA Sophia Antipolis},
    type = {Research Report},
    title = {Un algorithme d'allocation de bande passante satellitaire},
    year = {2004},
    number = {RR-5172},
    month = {April},
    address = {2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis},
    POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5172.ps.gz},
    PDF = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5172.pdf},
    URL = {http://www.inria.fr/rrrt/rr-5172.shtml},
    
    }
    

     
  2. J-C. Bermond, F. Havet, and C. D. Tóth. Fault tolerant on-board networks with priorities. Research Report RR-5363, INRIA, 2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis, November 2004. [WWW ] [PDF ] [POSTSCRIPT ]
    @TechReport{BHT04,
    author={J-C. Bermond and F. Havet and C. D. T\'oth},
    title={Fault tolerant on-board networks with priorities},
    institution = {INRIA},
    type = {Research Report},
    year = {2004},
    number = {RR-5363},
    month = {November},
    address = {2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis},
    POSTSCRIPT={ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5363.ps.gz},
    PDF = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5363.pdf},
    URL = {http://www.inria.fr/rrrt/rr-5363.shtml},
    
    }
    

     
  3. S. Bessy, E. Birmelé, and F. Havet. Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree. Research Report RR-5364, INRIA, 2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis, November 2004. [WWW ] [PDF ] [POSTSCRIPT ]
    @TechReport{BBH04,
    author={Bessy, S. and Birmel\'e, E. and F. Havet},
    title={Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree},
    institution = {INRIA},
    type = {Research Report},
    year = {2004},
    number = {RR-5364},
    month = {November},
    address = {2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis},
    POSTSCRIPT={ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5364.ps.gz},
    PDF = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5364.pdf},
    URL = {http://www.inria.fr/rrrt/rr-5364.shtml},
    
    }
    

     
  4. S. Choplin, J. Galtier, and S. Pérennes. Optimal concave costs in the SDH context. Research Report RR-5201, INRIA, 2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis, May 2004. [WWW ] [PDF ] [POSTSCRIPT ]
    @TechReport{CGP04,
    author = {S. Choplin and J. Galtier and S. P\'erennes},
    title = {Optimal concave costs in the SDH context},
    institution = {INRIA},
    type = {Research Report},
    year = {2004},
    number = {RR-5201},
    month = {May},
    address = {2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis},
    POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5201.ps.gz},
    PDF = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5201.pdf},
    URL = {http://www.inria.fr/rrrt/rr-5201.shtml} 
    }
    

     
  5. C. Cooper, R. Klasing, and T. Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. Research Report, INRIA Research Report RR-5376 and I3S Research Report I3S/RR-2004-39-FR, 2004. [PDF ] [POSTSCRIPT ]
    @TechReport{CKR04,
    author = {C. Cooper and R. Klasing and T. Radzik},
    title = {A randomized algorithm for the joining protocol in dynamic distributed networks},
    institution = {INRIA Research Report RR-5376 and I3S Research Report I3S/RR-2004-39-FR},
    type = {Research Report},
    year = {2004},
    PDF = {http://www.i3s.unice.fr/~mh/RR/2004/RR-04.39-R.KLASING.pdf},
    POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5376.ps.gz},
    
    }
    

     
  6. A. Guitton and J. Moulierac. Scalable Tree Aggregation with a Large Number of Multicast Groups. Technical report 1663, Irisa, December 2004. [PDF ]
    Abstract:
    IP multicast is not widely deployed yet over Internet. This is mainly due to the forwarding entries scalability and control explosion problems. In this paper, we propose an algorithm called STA (Scalable Tree Aggregation) which reduces the number of trees by allowing several groups to be aggregated to the same tree: the less trees, the less forwarding entries and the less control messages to maintain trees. STA performs faster aggregations than previous aggregation algorithms by evaluating fewer trees for each group, while keeping the same performance. We show the scalability and the fastness of STA by extensive simulations and we compare its performance to the previous algorithm.

    @techreport{GM04,
    author= {A. Guitton and J. Moulierac},
    title= {{S}calable {T}ree {A}ggregation with a {L}arge {N}umber of {M}ulticast {G}roups},
    institution= {Irisa},
    number= {1663},
    year= {2004},
    month= {December},
    PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Joanna.Moulierac/pdf/guitton04scalable.pdf},
    ABSTRACT={IP multicast is not widely deployed yet over Internet. This is mainly due to the forwarding entries scalability and control explosion problems. In this paper, we propose an algorithm called STA (Scalable Tree Aggregation) which reduces the number of trees by allowing several groups to be aggregated to the same tree: the less trees, the less forwarding entries and the less control messages to maintain trees. STA performs faster aggregations than previous aggregation algorithms by evaluating fewer trees for each group, while keeping the same performance. We show the scalability and the fastness of STA by extensive simulations and we compare its performance to the previous algorithm.} 
    }
    

     
  7. F. Havet and J.-S. Sereni. Improper choosability of graphs and maximum average degree. Research report, INRIA Research Report 5164 and I3S Research Report I3S/RR-2004-11-FR, April 2004. [WWW ] [PDF ] [POSTSCRIPT ]
    @TechReport{HaSe04,
    AUTHOR = {F. Havet and J.-S. Sereni},
    TITLE = {Improper choosability of graphs and maximum average degree},
    institution= {INRIA Research Report 5164 and I3S Research Report I3S/RR-2004-11-FR},
    MONTH = {April},
    YEAR = {2004},
    POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5164.ps.gz},
    pdf = {ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5164.pdf},
    URL={http://www.inria.fr/rrrt/rr-5164.shtml},
    type = {Research report},
    
    }
    

     
  8. R. Klasing, Z. Lotker, A. Navarra, and S. Pérennes. The Points and Vertices Game. Research Report TRCS 030/2004, Dipartimento di Informatica, Università degli Studi di L'Aquila, 2004. [PDF ] [POSTSCRIPT ]
    @techreport{KLNP04,
    title= {The Points and Vertices Game},
    author= {R. Klasing and Z. Lotker and A. Navarra and S. P\'erennes},
    year= {2004},
    number= {TRCS 030/2004},
    institution= {Dipartimento di Informatica, Universit\`a degli Studi di L'Aquila},
    type = {Research Report},
    pdf= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/KLNP04.pdf },
    POSTSCRIPT= { ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/KLNP04.ps },
    
    }
    

     
  9. R. Klasing, N. Morales, and S. Pérennes. On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands. Research Report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, 2004.
    Note: Submitted to Theoretical Computer Science. [PDF ] [POSTSCRIPT ]
    @TechReport{KMP04,
    author = {R. Klasing and N. Morales and S. P\'erennes},
    title = {On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands},
    institution = {INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR},
    type = {Research Report},
    year = {2004},
    PDF = {http://www.i3s.unice.fr/~mh/RR/2004/RR-04.40-R.KLASING.pdf},
    POSTSCRIPT = {ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-5432.ps.gz},
    note={Submitted to Theoretical Computer Science},
    
    }
    

     
  10. J.-F. Lalande, M. Syska, and Y. Verhoeven. Mascopt - A Network Optimization Library: Graph Manipulation. Technical report RT-0293, INRIA Sophia Antipolis, 2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis, April 2004. [WWW ] [PDF ] [POSTSCRIPT ]
    @TechReport{LSV04,
    author = {J.-F. Lalande and M. Syska and Y. Verhoeven},
    institution = {INRIA Sophia Antipolis},
    title = {Mascopt - A Network Optimization Library: Graph Manipulation},
    year = {2004},
    number = {RT-0293},
    month = {April},
    address = {2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis},
    POSTSCRIPT = {ftp://ftp-sop.inria.fr/pub/rapports/RT-0293.ps.gz},
    PDF = {ftp://ftp-sop.inria.fr/pub/rapports/RT-0293.pdf},
    URL = {http://www-sop.inria.fr/rapports/sophia/RT-0293.shtml},
    
    }
    

     
  11. A. Navarra. Tighter Bounds for the Minimum Energy Broadcasting problem. Research Report TRCS 033/2004, Dipartimento di Informatica, Università degli Studi di L'Aquila, 2004.
    @TechReport{Nav04,
    author={A. Navarra},
    title={Tighter Bounds for the Minimum Energy Broadcasting problem},
    year= { 2004 },
    number= { TRCS 033/2004 },
    institution= { Dipartimento di Informatica, Universit\`a degli Studi di L'Aquila },
    type = {Research Report},
    
    }
    

     
Miscellaneous
  1. L. Braud. Groupage de trafic sur le chemin. Rapport de stage de Magistère d'Informatique, 2 mois, encadrant D. Coudert, ENS Lyon, 2004. [PDF ]
    @MastersThesis{Bra04,
    author = {L.~Braud},
    title = {Groupage de trafic sur le chemin},
    type = {{Rapport de stage de Magist\`ere d'Informatique, 2 mois, encadrant D.~Coudert}},
    school={ENS Lyon},
    year = {2004},
    PDF={ftp://fpt-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_braud.pdf} 
    }
    

     
  2. A. Davert. Reroutage incrémental sur réseau optique. Rapport de stage de DEA RSD, 4 mois, encadrant D. Coudert, Université de Nice Sophia-Antipolis, 2004. [PDF ]
    @MastersThesis{Dav04,
    author = {A.~Davert},
    title = {Reroutage incr\'emental sur r\'eseau optique},
    type = {{Rapport de stage de DEA RSD, 4 mois, encadrant D.~Coudert}},
    school={Universit\'e de Nice Sophia-Antipolis},
    year = {2004},
    PDF={ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_davert.pdf} 
    }
    

     
  3. L. Jouhet. Protocole CDMA pour les réseaux Ad Hoc. Rapport de stage de Magistère d'Informatique, 2 mois, encadrant H. Rivano, ENS Lyon, 2004. [PDF ]
    @MastersThesis{Jou04,
    author = {L.~Jouhet},
    title = {Protocole CDMA pour les r\'eseaux Ad Hoc},
    type = {{Rapport de stage de Magist\`ere d'Informatique, 2 mois, encadrant H.~Rivano}},
    school={ENS Lyon},
    year = {2004},
    PDF={ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_jouhet.pdf} 
    }
    

     
  4. C. Mosse. Implémentation d'algorithmes pour les réseaux optiques WDM. Rapport de fin d'études d'Elève Ingénieur Maître, 4 mois, encadrants D. Coudert et M. Syska, IUP GMI d'Avignon, 2004. [PDF ]
    @MastersThesis{Mos04,
    author = {C.~Mosse},
    title = {Impl\'ementation d'algorithmes pour les r\'eseaux optiques {WDM}},
    type = {{Rapport de fin d'\'etudes d'El\`eve Ing\'enieur Ma\^itre, 4 mois, encadrants D.~Coudert et M.~Syska}},
    school={IUP GMI d'Avignon},
    year = {2004},
    PDF={ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_mosse.pdf} 
    }
    

     
  5. Q. C. Pham. Etude d'un problème algorithmique intervenant dans la reconfiguration des réseaux WDM. Rapport de stage de Magistère d'Informatique, 2 mois, encadrants D. Coudert et S. Pérennes, ENS Paris, 2004. [POSTSCRIPT ]
    @MastersThesis{Pha04,
    author = {Q.~C.~Pham},
    title = {Etude d'un probl\`eme algorithmique intervenant dans la reconfiguration des r\'eseaux {WDM}},
    type = {{Rapport de stage de Magist\`ere d'Informatique, 2 mois, encadrants D.~Coudert et S.~P\'erennes}},
    school={ENS Paris},
    year = {2004},
    POSTSCRIPT={ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_pham.ps.gz} 
    }
    

     
  6. L. Samper. A Markovian approach of the hidden terminal problem in IEEE 802.11. Rapport de stage de DEA MDFI, 4 mois, encadrant J. Galtier, Université de Luminy, Marseille, 2004. [POSTSCRIPT ]
    @MastersThesis{Sam04,
    author = {L. Samper},
    title = {A Markovian approach of the hidden terminal problem in {IEEE} 802.11},
    type = {Rapport de stage de DEA MDFI, 4 mois, encadrant J. Galtier},
    school={Universit\'e de Luminy, Marseille},
    year = {2004},
    POSTSCRIPT = {ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_samper.ps},
    
    }
    

     
  7. A. Schwing. Estimation fine du trafic urbain à partir de capteurs mobiles. Rapport de Mastère, 2 mois, encadrant P. Mussi, EPU Marseille, 2004. [PDF ]
    @MastersThesis{Sch04,
    author = {A.~Schwing},
    title = {Estimation fine du trafic urbain \`a partir de capteurs mobiles},
    type = {{Rapport de Mast\`ere, 2 mois, encadrant P. Mussi}},
    school={EPU Marseille},
    year = {2004},
    PDF = {ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_schwing.pdf},
    
    }
    

     
  8. J. Serror. Réseaux d'interconnexion : tolérance aux pannes. Rapport de stage de Maîtrise, 2 mois, encadrant J-C. Bermond, ENS Paris, 2004. [POSTSCRIPT ]
    @MastersThesis{Ser04,
    author = {J.~Serror},
    title = {R\'eseaux d'interconnexion : tol\'erance aux pannes},
    type = {{Rapport de stage de Ma\^itrise, 2 mois, encadrant J-C.~Bermond}},
    school={ENS Paris},
    year = {2004},
    POSTSCRIPT={ftp://ftp-sop.inria.fr/mascotte/Stages/Rapports-2003-2004/rapport_serror.ps.gz} 
    }
    

     

BACK TO COATI PUBLICATION INDEX



Last modified: Sat Jan 29 19:00:42 2022