MASCOTTE no longer exists => visit the new COATI project-team
 

Publications of year 2003
BACK TO MASCOTTE PUBLICATION INDEX

Publications of year 2003

Books and proceedings
  1. B. Reed and C. Linhares-Sales, editors. Recent advances in algorithms and combinatorics, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 11. Springer-Verlag, New York, 2003. 
    @book {MR1952980,
TITLE = {Recent advances in algorithms and combinatorics},
SERIES = {CMS Books in Mathematics/Ouvrages de Math\'ematiques de la SMC, 11},
EDITOR = {Reed, B. and Linhares-Sales, C.},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2003},
PAGES = {xiv+351},

}

Thesis
  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. [WWW ] [PDF ] [POSTSCRIPT ]
    Abstract:
    Cette thèse s'intéresse aux problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux d'infrastructure de télécommunication. L'optimisation de ces réseaux est essentielle aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées. Nous donnons une nouvelle modélisation des réseaux optiques WDM multifibres. En considérant un routage agrégé au niveau des câbles, nous optons pour une nouvelle lecture des contraintes d'affectation de longueurs d'onde fondée sur des conflits de groupe. Nous étudions aussi le problème de coloration de chemins, issu de l'affectation de longueurs d'onde dans les réseaux optiques monofibres. Nous développons, pour la relaxation linéaire de ce problème, un algorithme polynomial efficace dans les arbres de degré borné, puis, par extension, dans les graphes de largeur arborescente bornée. Nous majorons le coût d'une telle coloration dans les arbres binaires et donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la coloration entière dans les arbres de degré borné, ce qui améliore le meilleur algorithme connu pour ce cas. Nous présentons enfin des avancées algorithmiques pour les problèmes de multiflot entier et fractionnaire. Nous donnons un algorithme d'arrondi aléatoire incrémental pour l'approximation du multiflot entier. Motivés par le besoin d'un calcul rapide de multiflot fractionnaire pour l'algorithme précédent, nous nous intéressons aux approximations combinatoires de ce problème. En employant des techniques de calcul dynamique des plus courts chemins, nous améliorons l'un des meilleurs algorithme de la littérature. 

    @PHDTHESIS{Riv03,
author = {H. Rivano},
title = {Algorithmique et télécommunications : coloration et multiflot approchés et applications aux réseaux d'infrastructure},
school = {Université de Nice-Sophia Antipolis},
year = {2003},
month = {November},
abstract = {Cette thèse s'intéresse aux problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux d'infrastructure de télécommunication. L'optimisation de ces réseaux est essentielle aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées. Nous donnons une nouvelle modélisation des réseaux optiques WDM multifibres. En considérant un routage agrégé au niveau des câbles, nous optons pour une nouvelle lecture des contraintes d'affectation de longueurs d'onde fondée sur des conflits de groupe. Nous étudions aussi le problème de coloration de chemins, issu de l'affectation de longueurs d'onde dans les réseaux optiques monofibres. Nous développons, pour la relaxation linéaire de ce problème, un algorithme polynomial efficace dans les arbres de degré borné, puis, par extension, dans les graphes de largeur arborescente bornée. Nous majorons le coût d'une telle coloration dans les arbres binaires et donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la coloration entière dans les arbres de degré borné, ce qui améliore le meilleur algorithme connu pour ce cas. Nous présentons enfin des avancées algorithmiques pour les problèmes de multiflot entier et fractionnaire. Nous donnons un algorithme d'arrondi aléatoire incrémental pour l'approximation du multiflot entier. Motivés par le besoin d'un calcul rapide de multiflot fractionnaire pour l'algorithme précédent, nous nous intéressons aux approximations combinatoires de ce problème. En employant des techniques de calcul dynamique des plus courts chemins, nous améliorons l'un des meilleurs algorithme de la littérature.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/these.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/these.ps.gz},
url = {http://www-sop.inria.fr/mascotte/Herve.Rivano/?lang=fr&to_inc=thesis.php} 
}

  2. C. Touati. Les principes d'équité appliqués aux réseaux de télécommunications. PhD thesis, Université de Nice-Sophia Antipolis, September 2003. 
    @PhdThesis{Tou03,
author = {C. Touati},
title = {Les principes d'\'equit\'e appliqu\'es aux r\'eseaux de t\'el\'ecommunications},
school = {Universit\'e de Nice-Sophia Antipolis},
year = {2003},
month = {September} 
}

Articles in journal or book chapters
  1. D. Coudert and X. Muñoz. Recent Research Developments in Optics, 3, chapter 37, Graph Theory and Traffic Grooming in WDM Rings, pages 759-778. Research Signpost. Kerala, India, 2003.
    Note: ISBN: 81-271-0028-5. [PDF ] [POSTSCRIPT ]
    Abstract:
    This paper has a double purpose. In the first part of the paper we give an overview of different aspects of graph theory which can be applied in communication engineering, not trying to present immediate results to be applied neither a complete survey of results, but to give a flavor of how graph theory can help research in optical networks. The second part of this paper is a detailed example of the usage of graph theory, but it is also a complete survey of recent results in minimization of the number of add--drop multiplexers (ADMs) required in a WDM ring with traffic grooming. 

    @INBOOK{CoMu03,
chapter = {37, Graph Theory and Traffic Grooming in WDM Rings},
pages = {759-778},
title = {Recent Research Developments in Optics, 3},
publisher = {Research Signpost. Kerala, India},
year = {2003},
author = {D. Coudert and X. Mu{\~n}oz},
note = {ISBN: 81-271-0028-5},
abstract = { This paper has a double purpose. In the first part of the paper we give an overview of different aspects of graph theory which can be applied in communication engineering, not trying to present immediate results to be applied neither a complete survey of results, but to give a flavor of how graph theory can help research in optical networks. The second part of this paper is a detailed example of the usage of graph theory, but it is also a complete survey of recent results in minimization of the number of add--drop multiplexers (ADMs) required in a WDM ring with traffic grooming.},
optnumber = {3},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CoMu03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CoMu03.ps.gz} 
}

  2. B. Reed. Algorithmic aspects of tree width. In Recent advances in algorithms and combinatorics, volume 11 of CMS Books Math./Ouvrages Math. SMC, pages 85--107. Springer, New York, 2003. 
    @incollection {MR1952984,
AUTHOR = {Reed, B.},
TITLE = {Algorithmic aspects of tree width},
BOOKTITLE = {Recent advances in algorithms and combinatorics},
SERIES = {CMS Books Math./Ouvrages Math. SMC},
VOLUME = {11},
PAGES = {85--107},
PUBLISHER = {Springer},
ADDRESS = {New York},
YEAR = {2003},

}

  3. 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. [PDF ] 
    @Article{BBPY03,
Author= {R. Balakhrishnan and J.-C. Bermond and P. Paulraja and M.-L. Yu},
Title= {On Hamilton cycle decompositions of the tensor product of complete graphs},
Year={2003},
Journal={Discrete Mathematics},
Volume= {268},
Pages={49--58},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BBPY03.pdf},

}

  4. O. Barrientos, R. Correa, P. Reyes, and A. Valdebenito. A Branch and Bound Method for Solving Integer Separable Concave Problems. Comput. Optim. Appl., 26(2):155--171, 2003. [WWW ] [PDF ]
    Abstract:
    A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported. 

    @article{BCRV03,
author = {O. Barrientos and R. Correa and P. Reyes and A. Valdebenito},
title = {A Branch and Bound Method for Solving Integer Separable Concave Problems},
journal = {Comput. Optim. Appl.},
volume = {26},
number = {2},
year = {2003},
issn = {0926-6003},
pages = {155--171},
url = {http://dx.doi.org/10.1023/A:1025746430535},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/BCRV03.pdf},
publisher = {Kluwer Academic Publishers},
address = {Norwell, MA, USA},
abstract = {A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.},

}

  5. J.-C. Bermond, J. Bond, D. Peleg, and S. Pérennes. The power of small coalitions in graphs. Discrete Applied Mathematics, Editor's Choice, 127(3):399-414, 2003. [PDF ] 
    @Article{BBPP03,
author = {J.-C. Bermond and J. Bond and D. Peleg and S. P\'erennes},
title = {The power of small coalitions in graphs},
journal = {Discrete Applied Mathematics, Editor's Choice},
year = {2003},
Volume= {127},
number={3},
Pages={399-414},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BBPP03.pdf},

}

  6. J.-C. Bermond and S. Ceroi. Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3. Networks, 41(2):83--86, 2003. [PDF ] 
    @Article{BeCe03,
author = {J.-C. Bermond and S. Ceroi},
title = {Minimizing {SONET ADM}s in unidirectional {WDM} rings with grooming ratio 3},
journal = {Networks},
year = {2003},
Volume= {41},
Number= {2},
Pages={83--86},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BeCe03.pdf},

}

  7. J.-C. Bermond, S. Choplin, and S. Pérennes. Hierarchical ring networks design. Theory of Computing Systems, 36(6):663--682, 2003. [PDF ] 
    @article{BCP03,
author= { J.-C. Bermond and S. Choplin and S. P\'erennes },
title= { Hierarchical ring networks design },
journal= { Theory of Computing Systems },
year= { 2003 },
volume= { 36 },
number = {6},
pages= { 663--682 },
pdf= { ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BCP03.pdf },

}

  8. J-C. Bermond, D. Coudert, and M-L. Yu. On DRC-Covering of $K_n$ by cycles. Journal of Combinatorial Designs, 11(2):100-112, 2003. [WWW ] [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. 

    @ARTICLE{BCY03,
author = {J-C. Bermond and D. Coudert and M-L. Yu},
title = {{On DRC-Covering of $K_n$ by cycles}},
journal = {Journal of Combinatorial Designs},
year = {2003},
volume = {11},
pages = {100-112},
number = {2},
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.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCY-JCD03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCY-JCD03.ps.gz},
url = {http://dx.doi.org/10.1002/jcd.10040} 
}

  9. J.-C. Bermond, M. Di Ianni, M. Flammini, and S. Pérennes. Acyclic orientations for deadlock prevention in usual networks. Discrete Applied Mathematics, 129(1):31--47, 2003. [PDF ] 
    @article{BFIP03,
author= { J.-C. Bermond and M. {Di Ianni} and M. Flammini and S. P\'erennes },
title= { Acyclic orientations for deadlock prevention in usual networks },
year= { 2003 },
journal= { Discrete Applied Mathematics },
volume= { 129 },
number = {1},
pages= { 31--47 },
pdf= { ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BDFP03.pdf },

}

  10. J.-C. Bermond, N. Marlin, D. Peleg, and S. Pérennes. Directed Virtual Path Layout in ATM networks. Theoretical Computer Science, 291(1):3--28, 2003. [PDF ] 
    @article{BMPP03,
author= { J.-C. Bermond and N. Marlin and D. Peleg and S. P\'erennes },
title= { Directed Virtual Path Layout in {ATM} networks },
journal= { Theoretical Computer Science },
year= { 2003 },
volume= { 291 },
number = {1},
pages= { 3--28 },
pdf={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BMPP03.pdf},

}

  11. B. Bui-Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(2):267--285, April 2003. 
    @ARTICLE{BFJ03a,
AUTHOR = {B. Bui-Xuan and A. Ferreira and A. Jarry},
JOURNAL = {International Journal of Foundations of Computer Science},
MONTH = {April},
NUMBER = {2},
PAGES = {267--285},
TITLE = {Computing shortest, fastest, and foremost journeys in dynamic networks},
VOLUME = {14},
YEAR = {2003},
OPTnote = {},
OPTannote = {} 
}

  12. G. Calinescu, C. G. Fernandes, and B. Reed. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J. Algorithms, 48(2):333--359, 2003. 
    @article {MR1999215,
AUTHOR = {C{\u{a}}linescu, G. and Fernandes, C. G. and Reed, B.},
TITLE = {Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width},
JOURNAL = {J. Algorithms},
VOLUME = {48},
YEAR = {2003},
NUMBER = {2},
PAGES = {333--359},

}

  13. H. Cirstea, C. Kirchner, L. Liquori, and B. Wack. Rewrite strategies in the Rewriting Calculus. WRS, International Workshop on Reduction Strategies in Rewriting and Programming. Electr. Notes Theor. Comput. Sci., 86(4), 2003. [POSTSCRIPT ] 
    @article{CKLW03,
author = {H. Cirstea and C. Kirchner and L. Liquori and B. Wack},
title = {{Rewrite strategies in the Rewriting Calculus}},
journal = {WRS, International Workshop on Reduction Strategies in Rewriting and Programming. Electr. Notes Theor. Comput. Sci.},
volume = {86},
number = {4},
year = {2003},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/wrs-03.ps.gz} 
}

  14. A. Clementi, A. Ferreira, P. Penna, S. Pérennes, and R. Silvestri. The Minimum Range Assignment Problem on Linear Radio Networks. Algorithmica, 35(2):95--110, 2003. 
    @ARTICLE{CFPP+03,
AUTHOR = {A. Clementi and A. Ferreira and P. Penna and S. P\'erennes and R. Silvestri},
JOURNAL = {Algorithmica},
KEY = {j},
NUMBER = {2},
PAGES = {95--110},
TITLE = {{The Minimum Range Assignment Problem on Linear Radio Networks}},
VOLUME = {35},
YEAR = {2003},

}

  15. A. Ferreira, S. Pérennes, 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. [WWW ] [PDF ]
    Abstract:
    In this paper, we study multi-fiber optical networks with wavelength division multiplexing (WDM). We extend the definition of the well-known Wavelength Assignment Problem (WAP) to the case of k fibers per link and w wavelengths per fiber, generalization that we will call (k,w)-WAP. We develop a new model for the (k,w)-WAP based on conflict hypergraphs. Furthermore, we consider two natural optimization problems that arise from the (k,w)-WAP: minimizing the number of fibers k given a number of wavelengths w, on one hand, and minimizing w given k, on the other. We develop and analyze the practical performance of two methodologies based on hypergraph coloring. 

    @article{FPRR+03,
author= { A. Ferreira and S. P\'erennes and A. W. Richa and H. Rivano and N. Stier },
title= { Models, Complexity and Algorithms for the Design of Multi-fiber WDM Networks },
journal= { Telecommunication Systems },
year= { 2003 },
volume= { 24 },
pages= { 123--138 },
number= { 2 },
month= { October },
abstract= { In this paper, we study multi-fiber optical networks with wavelength division multiplexing (WDM). We extend the definition of the well-known Wavelength Assignment Problem (WAP) to the case of k fibers per link and w wavelengths per fiber, generalization that we will call (k,w)-WAP. We develop a new model for the (k,w)-WAP based on conflict hypergraphs. Furthermore, we consider two natural optimization problems that arise from the (k,w)-WAP: minimizing the number of fibers k given a number of wavelengths w, on one hand, and minimizing w given k, on the other. We develop and analyze the practical performance of two methodologies based on hypergraph coloring. },
pdf= { ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/fprrs03a.pdf },
url= { http://www.springerlink.com/content/m38310658021/ },

}

  16. J. Galtier, F. Hurtado, M. Noy, S. Pérennes, and J. Hurrutia. Simultaneous edge flipping in triangulations. International Journal of Computational Geometry and Applications, 13(2):113--133, 2003. 
    @Article{GHHN+03,
author = {J. Galtier and F. Hurtado and M. Noy and S. P\'erennes and J. Hurrutia},
title = {Simultaneous edge flipping in triangulations},
journal = {International Journal of Computational Geometry and Applications},
year = {2003},
volume = {13},
number = {2},
pages = {113--133} 
}

  17. O. Goldschmidt, A. Laugier, and E. Olinick. SONET/SDH ring assignment with capacity constraints. Discrete Applied Math., 129:99--128, June 2003. [PDF ] 
    @article{GLO03,
author = {O. Goldschmidt and A. Laugier and E. Olinick},
title = {SONET/SDH ring assignment with capacity constraints},
journal = {Discrete Applied Math.},
volume = {129},
pages = {99--128},
month = {June},
year = {2003},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/GLO03.pdf},

}

  18. F. Havet. On unavoidability of trees with $k$ leaves. Graphs and Combinatorics, 19:101--110, 2003. [PDF ] 
    @ARTICLE {Hav03,
AUTHOR = "F. Havet",
TITLE = "On unavoidability of trees with $k$ leaves",
JOURNAL = "Graphs and Combinatorics",
VOLUME = "19",
YEAR = "2003",
PAGES = "101--110",
PDF = "ftp://ftp-sop.inria.fr/mascotte/Publications/Hav03.pdf",

}

  19. M. Loebl, J. Nesetril, and B. Reed. A note on random homomorphism from arbitrary graphs to $\mathbb Z$. Discrete Math., 273(1-3):173--181, 2003.
    Note: EuroComb'01 (Barcelona). 
    @article {MR2025948,
AUTHOR = {Loebl, M. and Ne{\v{s}}et{\v{r}}il, J. and Reed, B.},
TITLE = {A note on random homomorphism from arbitrary graphs to {$\mathbb Z$}},
NOTE = {EuroComb'01 (Barcelona)},
JOURNAL = {Discrete Math.},
VOLUME = {273},
YEAR = {2003},
NUMBER = {1-3},
PAGES = {173--181},

}

  20. C. McDiarmid and B. Reed. Channel assignment on graphs of bounded treewidth. Discrete Math., 273(1-3):183--192, 2003.
    Note: EuroComb'01 (Barcelona). 
    @article {MR2025949,
AUTHOR = {McDiarmid, C. and Reed, B.},
TITLE = {Channel assignment on graphs of bounded treewidth},
NOTE = {EuroComb'01 (Barcelona)},
JOURNAL = {Discrete Math.},
VOLUME = {273},
YEAR = {2003},
NUMBER = {1-3},
PAGES = {183--192},

}

  21. B. Reed. The height of a random binary search tree. J. ACM, 50(3):306--332 (electronic), 2003. 
    @article {MR2146357,
AUTHOR = {Reed, B.},
TITLE = {The height of a random binary search tree},
JOURNAL = {J. ACM},
VOLUME = {50},
YEAR = {2003},
NUMBER = {3},
PAGES = {306--332 (electronic)},

}

  22. C. Touati, E. Altman, and J. Galtier. Semi-definite programming approach for bandwidth allocation and routing in networks. Game Theory and Applications, 9:169--179, 2003. 
    @Article{TAG03c,
author = {C. Touati and E. Altman and J. Galtier},
title = {Semi-definite programming approach for bandwidth allocation and routing in networks},
journal = {Game Theory and Applications},
pages = {169--179},
publisher = {Nova},
year = {2003},
volume = {9},

}

Conference articles
  1. E. Altman, I. Buret, B. Fabre, J. Galtier, C. Guiraud, T. Tocker, and C. Touati. 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. [PDF ] 
    @InProceedings{ABF+03,
author = {E. Altman and I. Buret and B. Fabre and J. Galtier and C. Guiraud and T. Tocker and C. Touati},
title = {Slot allocation in a {TDMA} satellite system: simulated annealing approach},
booktitle = {Proceedings of AIAA International Communication Satellite Systems Conference and Exhibit},
year = {2003},
address = {Yokohama, Japan},
month = {April},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/ABF+03.pdf},

}

  2. E. Altman, J. Galtier, and C. Touati. Radio Planning in Multibeam Geostationary Satellite Networks. In Proceedings of AIAA International Communication Satellite Systems Conference and Exhibit, Yokohama, Japan, April 2003. [PDF ] 
    @InProceedings{AGT03b,
author = {E. Altman and J. Galtier and C. Touati},
title = {Radio Planning in Multibeam Geostationary Satellite Networks},
booktitle = {Proceedings of AIAA International Communication Satellite Systems Conference and Exhibit},
year = {2003},
address = {Yokohama, Japan},
month = {April},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AGT03b.pdf},

}

  3. E. Altman, J. Galtier, and C. Touati. Semi-definite programming approach for bandwidth allocation and routing in networks. In Proceedings of ITC 18, Berlin, Germany, pages 1091--1100, August/September 2003. [PDF ] 
    @InProceedings{AGT03a,
author = {E. Altman and J. Galtier and C. Touati},
title = {Semi-definite programming approach for bandwidth allocation and routing in networks},
booktitle = {Proceedings of ITC 18},
year = {2003},
pages = {1091--1100},
address = {Berlin, Germany},
month = {August/September},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/AGT03a.pdf},

}

  4. G. Barthe, H. Cirstea, C. Kirchner, and L. Liquori. Pure Patterns Type Systems. In POPL, Symposium on Principles of Programming Languages, pages 250--261, 2003. ACM. [POSTSCRIPT ] 
    @inproceedings{BCKL03,
author = {G. Barthe and H. Cirstea and C. Kirchner and L. Liquori},
title = {{Pure Patterns Type Systems}},
booktitle = {{POPL, Symposium on Principles of Programming Languages}},
PUBLISHER = {ACM},
year = {2003},
pages = {250--261},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/popl-03.ps.gz} 
}

  5. R. Bayon, N. Lygeros, and J.-S. Sereni. Nouveaux progrès dans l'énumération des modèles mixtes. In Knowledge discovery and discrete mathematics : JIM'2003, Université de Metz, France, pages 243--246, 2003. INRIA. [WWW ] [PDF ] 
    @InProceedings{BLS03,
author = {R. Bayon and N. Lygeros and J.-S. Sereni},
title = {Nouveaux progr\`es dans l'\'enum\'eration des mod\`eles mixtes},
booktitle = {Knowledge discovery and discrete mathematics : JIM'2003},
pages = {243--246},
year = {2003},
PUBLISHER = {INRIA},
number = {},
series = {},
address = {Universit\'e de Metz, France},
URL={http://www.iut.univ-metz.fr/~esanjuan/JIM03/},
PDF={http://kam.mff.cuni.cz/~sereni/Articles/BLS03.pdf},

}

  6. J.-C. Bermond and D. Coudert. Traffic Grooming in Unidirectional WDM Ring Networks using Design Theory. In IEEE ICC, volume 2, Anchorage, Alaska, pages 1402-1406, May 2003.
    Note: ON07-3. [PDF ] [POSTSCRIPT ]
    Abstract:
    We address the problem of traffic grooming in WDM rings with all-to-all uniform unitary traffic. We want to minimize the total number of SONET add-drop multiplexers (ADMs) required. We show that this problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most $C$ edges (where $C$ is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for practical values and infinite congruence classes of values for a given $C$, and thus improve and unify all the preceding results. We disprove a conjecture of Chiu and Modiano (IEEE/OSA JLT 2000) saying that the minimum number of ADMs cannot be achieved with the minimum number of wavelengths, and also another conjecture of Hu (OSA JON 2002). 

    @INPROCEEDINGS{BeCo03,
author = {J.-C. Bermond and D. Coudert},
title = {Traffic Grooming in Unidirectional {WDM} Ring Networks using Design Theory},
booktitle = {IEEE ICC},
year = {2003},
volume = {2},
pages = {1402-1406},
address = {Anchorage, Alaska},
month = may,
note = {ON07-3},
abstract = { We address the problem of traffic grooming in WDM rings with all-to-all uniform unitary traffic. We want to minimize the total number of SONET add-drop multiplexers (ADMs) required. We show that this problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most $C$ edges (where $C$ is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for practical values and infinite congruence classes of values for a given $C$, and thus improve and unify all the preceding results. We disprove a conjecture of Chiu and Modiano (IEEE/OSA JLT 2000) saying that the minimum number of ADMs cannot be achieved with the minimum number of wavelengths, and also another conjecture of Hu (OSA JON 2002).},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BC-ICC03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BC-ICC03.ps.gz} 
}

  7. J.-C. Bermond, D. Coudert, and X. Muñoz. Traffic Grooming in Unidirectional WDM Ring Networks: The All-to-all Unitary Case. In The 7th IFIP Working Conference on Optical Network Design & Modelling -- ONDM, Budapest, Hongrie, pages 1135-1153, 2003. [PDF ] [POSTSCRIPT ]
    Abstract:
    We address the problem of traffic grooming in WDM rings with all-to-all uniform unitary traffic. We want to minimize the total number of SONET add-drop multiplexers (ADMs) required. This problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most $C$ edges (where $C$ is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for practical values and infinite congruence classes of values for a given $C$. Among others, we give optimal constructions when $C\geq N(N-1)/6$ and results when $C=12$. We also show how to improve lower bounds by using refined counting techniques, and how to use efficiently an ILP program by restricting the search space. 

    @INPROCEEDINGS{BCM03,
author = {J.-C. Bermond and D. Coudert and X. Mu{\~n}oz},
title = {Traffic Grooming in Unidirectional {WDM} Ring Networks: The All-to-all Unitary Case},
booktitle = {The 7th IFIP Working Conference on Optical Network Design \& Modelling -- ONDM},
year = {2003},
pages = {1135-1153},
address = {Budapest, Hongrie},
abstract = {We address the problem of traffic grooming in WDM rings with all-to-all uniform unitary traffic. We want to minimize the total number of SONET add-drop multiplexers (ADMs) required. This problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most $C$ edges (where $C$ is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for practical values and infinite congruence classes of values for a given $C$. Among others, we give optimal constructions when $C\geq N(N-1)/6$ and results when $C=12$. We also show how to improve lower bounds by using refined counting techniques, and how to use efficiently an ILP program by restricting the search space.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCM-ONDM03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCM-ONDM03.ps.gz} 
}

  8. J.-C. Bermond, O. DeRivoyre, S. Pérennes, and M. Syska. Groupage par tubes. In Conference ALGOTEL2003, Banyuls, May 2003, pages 169--174, 2003. [PDF ] 
    @InProceedings{BDPS03,
Author= {J.-C. Bermond and O. DeRivoyre and S. P\'erennes and M. Syska },
Title= {Groupage par tubes},
Year={2003},
Pages = {169--174},
BookTitle={Conference ALGOTEL2003, Banyuls, May 2003},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BDPS03.pdf},

}

  9. J.-C. Bermond, O. Delmas, F. Havet, M. Montassier, and S. Pérennes. Réseaux de télécommunications minimaux embarqués tolérants. In Conference ALGOTEL2003, Banyuls, May 2003, pages 27--32, 2003. [PDF ] 
    @InProceedings{BDH+03,
Author= {J.-C. Bermond and O. Delmas and F. Havet and M. Montassier and S. P\'erennes},
Title= {R\'eseaux de t\'el\'ecommunications minimaux embarqu\'es tol\'erants},
Year={2003},
Pages = {27--32},
BookTitle={Conference ALGOTEL2003, Banyuls, May 2003},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.Bermond/PUBLIS/BDH+03.pdf},

}

  10. 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. 
    @INPROCEEDINGS{BDF03,
AUTHOR = {P. Berthom\'e and M. Diallo and A. Ferreira},
BOOKTITLE = {Proceedings of WG'03},
MONTH = {June},
PAGES = {71--80},
PUBLISHER = {Springer-Verlag},
SERIES = {Lecture Notes in Computer Science},
TITLE = {Generalized Parametric Multi-Terminal Flows Problem},
VOLUME = {2880},
YEAR = {2003},

}

  11. S. Bhadra and A. Ferreira. Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks. In S. Pierre, M. Barbeau, and E. Kranakis, editors, Proceedings of Adhoc-Now'03, volume 2865 of Lecture Notes in Computer Science, Montreal, pages 259--270, October 2003. Springer Verlag. 
    @INPROCEEDINGS{BhFe03,
AUTHOR = {S. Bhadra and A. Ferreira},
ADDRESS = {Montreal},
BOOKTITLE = {Proceedings of Adhoc-Now'03},
MONTH = {October},
TITLE = {Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks},
YEAR = {2003},
pages = {259--270},
editor = {S. Pierre and M. Barbeau and E. Kranakis},
volume = {2865},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},

}

  12. 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 ]
    Abstract:
    The design of WDM optical networks is an issue for telecom operators since the spreading of this technology will not occur unless enough performance guarantees are provided. Motivated by the quest for efficient algorithms for the Routing and Wavelength Assignment problem (RWA), we address approximations of the fractional multicommodity flow problem which is the central part of a complex randomized rounding algorithm for the integral problem. Through the use of dynamic shortest path computations and other combinatorial approaches, we improve on the best known algorithm. We also provide directions for further improvements. 

    @INPROCEEDINGS{BCL+03,
author = {M. Bouklit and D. Coudert and J-F. Lalande and C. Paul and H. Rivano},
title = {Approximate multicommodity flow for {WDM} networks design},
booktitle = {SIROCCO 10},
year = {2003},
editor = {J. Sibeyn},
number = {17},
series = {Proceedings in Informatics},
pages = {43--56},
address = {Umea, Sweden},
publisher = {Carleton Scientific},
abstract = { The design of WDM optical networks is an issue for telecom operators since the spreading of this technology will not occur unless enough performance guarantees are provided. Motivated by the quest for efficient algorithms for the Routing and Wavelength Assignment problem (RWA), we address approximations of the fractional multicommodity flow problem which is the central part of a complex randomized rounding algorithm for the integral problem. Through the use of dynamic shortest path computations and other combinatorial approaches, we improve on the best known algorithm. We also provide directions for further improvements.},
optmonth = {#jun#},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCLPR-SIROCCO03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCLPR-SIROCCO03.ps.gz} 
}

  13. M. Bouklit, D. Coudert, J-F. Lalande, and H. Rivano. Approximation combinatoire de multiflot fractionnaire : améliorations. In AlgoTel'03, Banyuls-sur-mer, France, mai 2003. [PDF ] [POSTSCRIPT ]
    Abstract:
    Motiv\'e par la recherche d'algorithmes performants de dimensionnement de r\'eseaux optiques WDM, nous consid\'erons les $(1+\epsilon)$-approximations du calcul de multiflot fractionnaire. Nous proposons des am\'eliorations d'un algorithme de la litt\'erature en utilisant des calculs de plus courts chemins dynamiques, \'eventuellement sp\'ecialis\'e au cas du routage optique dans les r\'eseaux WDM multifibres sans conversion. 

    @INPROCEEDINGS{BCLR03,
author = {M. Bouklit and D. Coudert and J-F. Lalande and H. Rivano},
title = {Approximation combinatoire de multiflot fractionnaire : améliorations},
booktitle = {AlgoTel'03},
year = {2003},
address = {Banyuls-sur-mer, France},
month = mai,
abstract = {Motiv\'e par la recherche d'algorithmes performants de dimensionnement de r\'eseaux optiques WDM, nous consid\'erons les $(1+\epsilon)$-approximations du calcul de multiflot fractionnaire. Nous proposons des am\'eliorations d'un algorithme de la litt\'erature en utilisant des calculs de plus courts chemins dynamiques, \'eventuellement sp\'ecialis\'e au cas du routage optique dans les r\'eseaux WDM multifibres sans conversion.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCLR-AlgoTel03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCLR-AlgoTel03.ps.gz} 
}

  14. B. Bui-Xuan, A. Ferreira, and A. Jarry. Evolving graphs and least cost journeys in dynamic networks. In Proceedings of WiOpt'03 -- Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks, Sophia Antipolis, pages 141--150, March 2003. INRIA Press. 
    @INPROCEEDINGS{BFJ03b,
AUTHOR = {B. Bui-Xuan and A. Ferreira and A. Jarry},
ADDRESS = {Sophia Antipolis},
BOOKTITLE = {{Proceedings of WiOpt'03 -- Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks}},
MONTH = {March},
PAGES = {141--150},
PUBLISHER = {INRIA Press},
TITLE = {Evolving graphs and least cost journeys in dynamic networks},
YEAR = {2003},

}

  15. H.-J. Böckenhauer, D. Bongartz, J. Hromkovic, R. Klasing, G. Proietti, S. Seibert, and W. Unger. On $k$-Edge-Connectivity Problems with Sharpened Triangle Inequality (Extended Abstract). In Proc. 5th Italian Conference on Algorithms and Complexity ( CIAC 2003), volume 2653 of Lecture Notes in Computer Science, pages 189--200, 2003. Springer-Verlag. 
    @inproceedings{ BBH+03,
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 },
title= {On $k$-Edge-Connectivity Problems with Sharpened Triangle Inequality (Extended Abstract) },
booktitle= {Proc.\ 5th Italian Conference on Algorithms and Complexity ({\em CIAC~2003}) },
series= {Lecture Notes in Computer Science},
publisher={Springer-Verlag },
volume= {2653},
pages= {189--200},
year= {2003 },

}

  16. A. Ciaffaglione, L. Liquori, and M. Miculan. Imperative Object-Based Calculi in Co-inductive Type Theories. In LPAR, International Conference on Logic for Programming Artificial Intelligence and Reasoning, volume 2850 of Lecture Notes in Computer Science, pages 59--77, 2003. [PDF ] 
    @inproceedings{CLM03a,
author = {A. Ciaffaglione and L. Liquori and M. Miculan},
title = {Imperative Object-Based Calculi in Co-inductive Type Theories},
booktitle = {{LPAR, International Conference on Logic for Programming Artificial Intelligence and Reasoning}},
series = lncs,
VOLUME = {2850},
year = {2003},
pages = {59--77},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/lpar-03.pdf} 
}

  17. A. Ciaffaglione, L. Liquori, and M. Miculan. Reasoning on an imperative object-based calculus in Higher Order Abstract Syntax. In MERLIN, International Workshop on Mechanized Reasoning about Languages with Variable Binding, 2003. ACM. [PDF ] 
    @inproceedings{CLM03b,
author = {A. Ciaffaglione and L. Liquori and M. Miculan},
title = {Reasoning on an imperative object-based calculus in Higher Order Abstract Syntax},
booktitle = {{MERLIN, International Workshop on Mechanized Reasoning about Languages with Variable Binding}},
publisher = {ACM},
year = {2003},
PDF = {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/merlin-03.pdf} 
}

  18. H. Cirstea, L. Liquori, and B. Wack. Rewriting Calculus with Fixpoints: Untyped and First-order Systems. In TYPES, International Workshop on Types for Proof and Programs, volume 3085 of Lecture Notes in Computer Science, pages 147--161, 2003. Springer Verlag. [POSTSCRIPT ] 
    @INPROCEEDINGS{CLW03,
AUTHOR = {Cirstea,~H. and Liquori,~L. and Wack,~B.},
TITLE = {{Rewriting Calculus with Fixpoints: Untyped and First-order Systems}},
YEAR = {2003},
BOOKTITLE = {TYPES, International Workshop on Types for Proof and Programs},
series = lncs,
VOLUME = {3085},
PAGES = {147--161},
PUBLISHER = {Springer Verlag},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/types-03.ps.gz} 
}

  19. 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 Parallel and Distributed Processing Symposium (IPDPS), pages 8, April 2003. IEEE Computer Society Press. [WWW ] [PDF ]
    Abstract:
    We present a technique to evaluate the approximation ratio on random instances of the Minimum Energy Broadcast Problem in Ad-Hoc Radio Networks which is known to be NP-hard and approximable within 12. Our technique relies on polynomial-time computable lower bound on the optimal cost of any instance. The main result of this paper is that the approximation ratio has never achieved a value greater than 6.4. Furthermore, the worst values of this ratio are achieved for small network sizes. We also provide a clear geometrical motivation of such good approximation results. 

    @InProceedings{CHRV03,
author = {A. Clementi and G. Huiban and G. Rossi and Y. Verhoeven},
title = {On the approximation ratio of the {MST} based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks},
booktitle = {Parallel and Distributed Processing Symposium (IPDPS)},
pages = {8},
year = {2003},
month = {April},
publisher = {IEEE Computer Society Press},
OPTnote = {DOI 10.1109/IPDPS.2003.1213407},
url = {http://www.ipdps.org/ipdps2003/},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/CHRV03.pdf},
abstract = {We present a technique to evaluate the approximation ratio on random instances of the Minimum Energy Broadcast Problem in Ad-Hoc Radio Networks which is known to be NP-hard and approximable within 12. Our technique relies on polynomial-time computable lower bound on the optimal cost of any instance. 

The main result of this paper is that the approximation ratio has never achieved a value greater than 6.4. Furthermore, the worst values of this ratio are achieved for small network sizes. We also provide a clear geometrical motivation of such good approximation results.} 
}

  20. D. Coudert, H. Rivano, and X. Roche. A combinatorial approximation algorithm for the multicommodity flow problem. In K. Jansen and R. Solis-Oba, editors, WAOA 03, number 2909 of Lecture Notes in Computer Science, Budapest, Hungary, pages 256--259, September 2003. Springer-Verlag. [PDF ] [POSTSCRIPT ]
    Abstract:
    This work is motivated by the need for approximation algorithms for the integral multicommodity flow problem which arise in numerous optimization scenarios, including the design of telecommunication networks. We improve on one of the most efficient known combinatorial approximation algorithm for fractional multicommodity flow by using an incremental approach. This approach is validated by experimental results, which show a significant speed-up. 

    @INPROCEEDINGS{CRR03,
author = {D. Coudert and H. Rivano and X. Roche},
title = {A combinatorial approximation algorithm for the multicommodity flow problem},
booktitle = {WAOA 03},
year = {2003},
editor = {K. Jansen and R. Solis-Oba},
number = {2909},
series = {Lecture Notes in Computer Science},
pages = {256--259},
address = {Budapest, Hungary},
month = sep,
publisher = {Springer-Verlag},
abstract = { This work is motivated by the need for approximation algorithms for the integral multicommodity flow problem which arise in numerous optimization scenarios, including the design of telecommunication networks. We improve on one of the most efficient known combinatorial approximation algorithm for fractional multicommodity flow by using an incremental approach. This approach is validated by experimental results, which show a significant speed-up.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CRR-WAOA03.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CRR-WAOA03.ps.gz} 
}

  21. O. Dalle and P. Mussi. Cooperative Software Development and Computational Resource Sharing. In NMSC System Simulation Workshop, ESTEC, Noordwijk, The Netherlands, March 2003. European Space Agency. 
    @inproceedings{DaMu03,
AUTHOR = {O. Dalle and P. Mussi},
TITLE = {Cooperative Software Development and Computational Resource Sharing},
BOOKTITLE = {NMSC System Simulation Workshop},
YEAR = 2003,
ORGANIZATION = {European Space Agency},
MONTH = mar,
ADDRESS = {ESTEC, Noordwijk, The Netherlands} 
}

  22. A. Ferreira, S. Perennes, A.W. Richa, H. Rivano, and N. Stier Moses. Models, complexity and algorithms for the design of multifiber WDM networks. In Telecommunications, 2003. ICT 2003. 10th International Conference on, volume 1, pages 12--18, 23 Feb.-1 March 2003. [PDF ]
    Abstract:
    We study multifiber optical networks with wavelength division multiplexing (WDM). Assuming that the lightpaths use the same wavelength from source to destination, we extend the definition of the well-known wavelength assignment problem (WAP), to the case where there are k fibers per link, and w wavelengths per fiber are available: This generalization is called the (k,w)-WAP. We develop a new model for the (k,w)-WAP, based on conflict hypergraphs: conflict hypergraphs more accurately capture the lightpath interdependencies, generalizing the conflict graphs used for single-fiber networks. By relating the (k,w)-WAP with the hypergraph coloring problem, we prove that the former is NP-complete, and present further results with respect to the complexity of that problem. We consider the two natural optimization problems that arise from the (k,w)-WAP: the problem of minimizing k given w, and that of minimizing w given k. We develop and analyze the practical performances of two methodologies based on hypergraph coloring, one for each of the two optimization problems, on existing backbone networks in Europe and in the USA. The first methodology relies on two heuristics based on a randomized approximation algorithm and the second consists on an integer programming formulation. 

    @INPROCEEDINGS{FPR+03b,
author = {Ferreira, A. and Perennes, S. and Richa, A.W. and Rivano, H. and Stier Moses, N.},
title = {Models, complexity and algorithms for the design of multifiber WDM networks},
booktitle = {Telecommunications, 2003. ICT 2003. 10th International Conference on},
year = {2003},
volume = {1},
pages = {12--18},
month = {23 Feb.-1 March},
abstract = {We study multifiber optical networks with wavelength division multiplexing (WDM). Assuming that the lightpaths use the same wavelength from source to destination, we extend the definition of the well-known wavelength assignment problem (WAP), to the case where there are k fibers per link, and w wavelengths per fiber are available: This generalization is called the (k,w)-WAP. We develop a new model for the (k,w)-WAP, based on conflict hypergraphs: conflict hypergraphs more accurately capture the lightpath interdependencies, generalizing the conflict graphs used for single-fiber networks. By relating the (k,w)-WAP with the hypergraph coloring problem, we prove that the former is NP-complete, and present further results with respect to the complexity of that problem. We consider the two natural optimization problems that arise from the (k,w)-WAP: the problem of minimizing k given w, and that of minimizing w given k. We develop and analyze the practical performances of two methodologies based on hypergraph coloring, one for each of the two optimization problems, on existing backbone networks in Europe and in the USA. The first methodology relies on two heuristics based on a randomized approximation algorithm and the second consists on an integer programming formulation.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/fprrs03.pdf} 
}

  23. F. Giroire, A. Nucci, N. Taft, and C. Diot. Increasing the Robustness of IP Backbones in the Absence of Optical Level Protection. In Proceedings of the Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2003. [WWW ] [PDF ]
    Abstract:
    There are two fundamental technology issues that challenge the robustness of IP backbones. First, SONET protection is gradually being removed because of its high cost (while SONET framing is kept for failure detection purposes). Protection and restoration are provided by the IP layer that operates directly over a DWDM infrastructure. Second, ISPs are systematically forced to use the shortest distance path between two Points of Presence in order to meet their promised SLAs. In this context, IP backbones are extremely vulnerable to fiber cuts that can bring down a significant fraction of the IP routes. We propose two solutions (an ILP model and a heuristic algorithm) to optimally map a given IP topology onto a fiber infrastructure. The version of the mapping problem that we address incorporates a number of real constraints and requirements faced by carriers today. The optimal mapping maximizes the robustness of the network while maintaining the ISP's SLA delay requirements. In addition, our heuristic takes into consideration constraints such as a shortage of wavelengths and priorities among POPs and routes. The heuristic is evaluated on the Sprint backbone network. We illustrate the tradeoffs between the many requirements. 

    @InProceedings{GNTD03,
author = {F. Giroire and A. Nucci and N. Taft and C. Diot},
title = {Increasing the Robustness of IP Backbones in the Absence of Optical Level Protection},
booktitle = {Proceedings of the Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)},
year = {2003},
url = {http://www.sprintlabs.com/People/anucci/Papers/Infocom03.pdf},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/GNTD03.pdf},
abstract = {There are two fundamental technology issues that challenge the robustness of IP backbones. First, SONET protection is gradually being removed because of its high cost (while SONET framing is kept for failure detection purposes). Protection and restoration are provided by the IP layer that operates directly over a DWDM infrastructure. Second, ISPs are systematically forced to use the shortest distance path between two Points of Presence in order to meet their promised SLAs. In this context, IP backbones are extremely vulnerable to fiber cuts that can bring down a significant fraction of the IP routes. We propose two solutions (an ILP model and a heuristic algorithm) to optimally map a given IP topology onto a fiber infrastructure. The version of the mapping problem that we address incorporates a number of real constraints and requirements faced by carriers today. The optimal mapping maximizes the robustness of the network while maintaining the ISP's SLA delay requirements. In addition, our heuristic takes into consideration constraints such as a shortage of wavelengths and priorities among POPs and routes. The heuristic is evaluated on the Sprint backbone network. We illustrate the tradeoffs between the many requirements.},

}

  24. C. Gomes and G. Robson Mateus. Alocação de Caminhos Comutatos por Rótulo em Redes Multiplexadas por Comprimento de Onda. In SPG, 2003. 
    @INPROCEEDINGS{GM03,
AUTHOR = {C. Gomes and G. {Robson Mateus}},
TITLE = {Aloca\c c\~ao de Caminhos Comutatos por R\'otulo em Redes Multiplexadas por Comprimento de Onda},
BOOKTITLE = {SPG},
SCHOOL = {Minas Gerais Federal University, MG},
YEAR = {2003},

}

  25. A. Jarry and A. Laugier. Graphes 2-connexes à diamètre donné. In ROADEF 2003, number 5 of Proceedings in Informatics, Avignon, France, pages 102--104, June 2003. Université d'Avignon et des Pays de Vaucluse. 
    @InProceedings{JaLa03,
author = {A. Jarry and A. Laugier},
title = {Graphes 2-connexes \`a diam\`etre donn\'e},
booktitle = {ROADEF 2003},
pages = {102--104},
year = {2003},
PUBLISHER = {Universit\'e d'Avignon et des Pays de Vaucluse},
number = {5},
series = {Proceedings in Informatics},
address = {Avignon, France},
month = {June},

}

  26. J.-F. Lalande, S. Pérennes, and M. Syska. Groupage dans les réseaux dorsaux WDM. In ROADEF 2003, number 5 of Proceedings in Informatics, Avignon, France, pages 254--255, June 2003. Université d'Avignon et des Pays de Vaucluse. 
    @InProceedings{LPS03,
author = {J.-F. Lalande and S. P\'erennes and M. Syska},
title = {Groupage dans les r\'eseaux dorsaux {WDM}},
booktitle = {ROADEF 2003},
pages = {254--255},
year = {2003},
PUBLISHER = {Universit\'e d'Avignon et des Pays de Vaucluse},
number = {5},
series = {Proceedings in Informatics},
address = {Avignon, France},
month = {June},

}

  27. A. Laugier and S. Petat. Network Design and b-matching. In Proc. of International Network Optimization Conference, pages 374--379, 2003. [POSTSCRIPT ] 
    @INPROCEEDINGS{LaPe03,
AUTHOR = {A. Laugier and S. Petat},
BOOKTITLE = {Proc. of International Network Optimization Conference},
PAGES = {374--379},
TITLE = {Network Design and b-matching},
YEAR = {2003},
OPTsorte = {#colin},
POSTSCRIPT = {ftp://ftp-sop.inria.fr/mascotte/Publications/LaPe03.ps},

}

  28. E. Trajano, D. Guigue, E. Costa, C. Gomes, H. Almeida, K. Silva, and N. Cavalcanti. SOS - A Tool for the Automatic Segmentation of Musical Flows. In IX SBCM, 2003. 
    @INPROCEEDINGS{TGCG+03,
AUTHOR = {E. Trajano and D. Guigue and E. Costa and C. Gomes and H. Almeida and K. Silva and N. Cavalcanti},
TITLE = {SOS - A Tool for the Automatic Segmentation of Musical Flows},
BOOKTITLE = {IX SBCM},
SCHOOL = {Campinas, SP},
YEAR = {2003},

}

Internal reports
  1. F. Havet. Stable set meeting every longest path. Research Report, INRIA Research Report 5009 and I3S Research Report I3S/RR-2003-29-FR, 2003. [WWW ] [PDF ] 
    @TechReport{Hav03c,
AUTHOR = "F. Havet",
TITLE = "Stable set meeting every longest path",
institution = "INRIA Research Report 5009 and I3S Research Report I3S/RR-2003-29-FR",
YEAR = "2003",
type="Research Report",
URL = {http://www.inria.fr/rrrt/rr-5009.php},
PDF = {http://www.i3s.unice.fr/~mh/RR/2003/RR-03.29-F.HAVET.pdf},

}

  2. F. Havet. Upper bound for the span of (s,1)-total labelling of graphs. Research Report, INRIA Research Report 4816 and I3S Research Report I3S/RR-2003-13-FR, 2003. [WWW ] [PDF ] 
    @Techreport{Hav03b,
AUTHOR = "F. Havet",
TITLE = "Upper bound for the span of (s,1)-total labelling of graphs",
institution = "INRIA Research Report 4816 and I3S Research Report I3S/RR-2003-13-FR",
YEAR = "2003",
type="Research Report",
url = {http://www.inria.fr/rrrt/rr-4816.php},
PDF = {http://www.i3s.unice.fr/~mh/RR/2003/RR-03.13-F.HAVET.pdf},

}

Miscellaneous
  1. O. Dalle and O. Françoise. Building High Performance Communications Through the Virtual File System API. Solutions Linux International Conference, February 2003. 
    @misc{DaFr03,
AUTHOR = {Dalle, O. and Fran\c{c}oise, O.},
TITLE = {Building High Performance Communications Through the Virtual File System {API}},
HOWPUBLISHED = {Solutions Linux International Conference},
YEAR = {2003},
MONTH = {February},
address = {Paris},

}

Internship reports
  1. A. Acosta. MOEDIG : Environnement de simulation pour modèles à évènements discrets généralisés. Rapport de Magistère en Ingénierie Electronique et Informatique, 6 mois, encadrants O. Dalle et P. Mussi, ENS Bretagne, 2003. 
    @MastersThesis{Aco03,
author = {A.~Acosta},
title = {MOEDIG~: Environnement de simulation pour modèles à \'evènements discrets g\'en\'eralis\'es},
type = {Rapport de Magistère en Ing\'enierie Electronique et Informatique, 6 mois, encadrants O. Dalle et P. Mussi},
school={ENS Bretagne},
year = {2003},

}

  2. L. Esperet. Coloration $(d,1)$-totale et méthode probabiliste. Rapport de Magistère d'Informatique, 5 semaines, encadrant F. Havet, ENS Lyon, 2003. 
    @MastersThesis{Esp03,
author = {L.~Esperet},
title = {Coloration $(d,1)$-totale et m\'ethode probabiliste},
type = {Rapport de Magistère d'Informatique, 5 semaines, encadrant F. Havet},
school={ENS Lyon},
year = {2003},

}

  3. F. Giroire. Etude de Problèmes Combinatoires liés à l'Analyse du Génome : Séquençage et Polymorphisme. Internship report, DEA Algorithmique, Université Paris VI., 2003. [PDF ] 
    @mastersthesis{Gir03,
author = {F. Giroire},
title = {Etude de Probl\`emes Combinatoires li\'es \`a l'Analyse du G\'enome : S\'equen\c{c}age et Polymorphisme},
year = {2003},
school = {DEA Algorithmique, Universit\'e Paris VI.},
pdf = {http://www-sop.inria.fr/members/Frederic.Giroire/publis/Gir03.pdf},
abstract = {},

}

  4. G. Joutel. Synthèse de réseau. Rapport de Magistère d'Informatique, 6 semaines, encadrant J. Galtier, Université Claude Bernard, Lyon I, 2003. 
    @MastersThesis{Jou03,
author = {G.~Joutel},
title = {Synthèse de r\'eseau},
type = {Rapport de Magistère d'Informatique, 6 semaines, encadrant J. Galtier},
school={Universit\'e Claude Bernard, Lyon I},
year = {2003},

}

  5. N. Morales. Robust models for simultaneous open pit and underground mines. Rapport de stage Chilean pre-doc, 4 mois et 1/2, encadrant R. Klasing, 2003. 
    @MastersThesis{Mor03,
author = {N.~Morales},
title = {Robust models for simultaneous open pit and underground mines},
type = {Rapport de stage Chilean pre-doc, 4 mois et 1/2, encadrant R. Klasing},
year = {2003},

}

  6. A. Papadopoulos. Adaptive broadcast consumption (ABC), a new heuristic and new bounds for the minimum energy broadcast routing problem. Rapport de Master, Grèce, 6 mois, encadrant R. Klasing, 2003. 
    @MastersThesis{Pap03,
author = {A.~Papadopoulos},
title = {Adaptive broadcast consumption (ABC), a new heuristic and new bounds for the minimum energy broadcast routing problem},
type = {Rapport de Master, Gr\`ece, 6 mois, encadrant R. Klasing},
year = {2003},

}

  7. X. Roche. Approximation du multiflot fractionnaire. Rapport de Magistère d'Informatique, 5 semaines, encadrants D. Coudert et H. Rivano, ENS Lyon, 2003. 
    @MastersThesis{Roc03,
author = {X. Roche},
title = {Approximation du multiflot fractionnaire},
type = {Rapport de Magistère d'Informatique, 5 semaines, encadrants D. Coudert et H. Rivano},
school={ENS Lyon},
year = {2003},

}

  8. M.-E. Voge. Conception de réseaux SDH en anneaux. Rapport de DEA ROCO, 4 mois, encadrants M.Burlet et A.Laugier, INP Grenoble, 2003. 
    @MastersThesis{Vog03,
author = {M.-E.~Voge},
title = {Conception de r\'eseaux SDH en anneaux},
type = {Rapport de DEA ROCO, 4 mois, encadrants M.Burlet et A.Laugier},
school={INP Grenoble},
year = {2003},

}

  9. O. de Rivoyre. Optimisation du groupage dans les réseaux de télécommunication. Rapport de DEA RSD, 5 mois, encadrants J.-C. Bermond et M. Syska, Université de Nice Sophia-Antipolis, 2003. 
    @MastersThesis{Der03,
author = {O.~de~Rivoyre},
title = {Optimisation du groupage dans les r\'eseaux de t\'el\'ecommunication},
type = {Rapport de DEA RSD, 5 mois, encadrants J.-C. Bermond et M. Syska},
school={Universit\'e de Nice Sophia-Antipolis},
year = {2003},

}


BACK TO MASCOTTE PUBLICATION INDEX



Last modified: Thu Oct 10 14:10:00 2013

This document was translated from BibTEX by bibtex2html