
MASCOTTE no longer exists => visit the new projectteam
Publications of year 2002
BACK TO MASCOTTE PUBLICATION INDEX
Publications of year 2002

H. Alt and A. Ferreira, editors.
Proceedings of STACS 2002,
volume 2285 of Lecture Notes in Computer Science.
SpringerVerlag,
2002.
@BOOK{AlFe02,
EDITOR = {H. Alt and A. Ferreira},
PUBLISHER = {SpringerVerlag},
SERIES = {Lecture Notes in Computer Science},
TITLE = {{Proceedings of STACS 2002}},
VOLUME = {2285},
YEAR = {2002},
}

M. Molloy and B. Reed.
Graph colouring and the probabilistic method,
volume 23 of Algorithms and Combinatorics.
SpringerVerlag,
Berlin,
2002.
@book {MR1869439,
AUTHOR = {Molloy, M. and Reed, B.},
TITLE = {Graph colouring and the probabilistic method},
SERIES = {Algorithms and Combinatorics},
VOLUME = {23},
PUBLISHER = {SpringerVerlag},
ADDRESS = {Berlin},
YEAR = {2002},
PAGES = {xiv+326},
}

O. Dalle,
S. Frénot,
and M. Riveill, editors.
Cinquième Ecole d'Hiver des Télécommunications,
Golfe Juan, France,
December 2002.
INRIA  CNRS  Univ. de Nice,
INRIA.
@proceedings{DFR02,
TITLE = {Cinqui\`eme Ecole d'Hiver des T\'el\'ecommunications},
YEAR = 2002,
EDITOR = {Dalle, O. and Fr\'enot, S. and Riveill, M.},
ADDRESS = {Golfe Juan, France},
MONTH = dec,
PUBLISHER = {INRIA},
ORGANIZATION = {INRIA  CNRS  Univ. de Nice}
}

S. Choplin.
Dimensionnement de réseaux virtuels de télécommunication.
PhD thesis,
Université de Nice  Sophia Antipolis,
November 2002.
@PhdThesis{Cho02,
author = {S. Choplin},
title = {Dimensionnement de r\'eseaux virtuels de t\'el\'ecommunication},
school = {Universit\'e de Nice  Sophia Antipolis},
year = {2002},
month = nov,
}

L. Floriani.
Méthodes d'Analyse des Données Multivariables pour l'étude des Mécanismes des Heuristiques.
PhD thesis,
Université de NiceSophia Antipolis,
January 2002.
@PhdThesis{Flo02,
author = {L. Floriani},
title = {M\'ethodes d'Analyse des Donn\'ees Multivariables pour l'\'etude des M\'ecanismes des Heuristiques},
school = {Universit\'e de NiceSophia Antipolis},
year = {2002},
month = jan,
}

A. Laugier.
Cônes de Matrices et Programmation Mathématique : Quelques Applications.
PhD thesis,
Université de NiceSophia Antipolis,
March 2002.
@PhdThesis{Lau02,
AUTHOR={A. Laugier},
TITLE={C\^{o}nes de Matrices et Programmation Math\'{e}matique : Quelques Applications},
MONTH= mar,
SCHOOL={Université de NiceSophia Antipolis},
OPTTYPE={Thèse de Doctorat},
YEAR={2002},
}

M. Cosnard.
Introduction to the Complexity of Parallel Algorithms.
In R. Corrêa,
I. Dutra,
M. Fiallos,
and F. Gomes, editors,Parallel and Distributed Algorithms: Theory, Algorithmic Techniques and Applications,
Applied Optimization,
chapter 1, part I,
pages 325.
Kluwer Academic Publishers,
Boston (USA),
2002.
@InCollection{Cos02,
author = {M. Cosnard},
editor = {R. Corrêa and I. Dutra and M. Fiallos and F. Gomes},
title = {Introduction to the Complexity of Parallel Algorithms},
booktitle = {Parallel and Distributed Algorithms: {T}heory, Algorithmic Techniques and Applications},
chapter = {1, part I},
publisher = {Kluwer Academic Publishers},
year = {2002},
series = {Applied Optimization},
address = {Boston (USA)},
pages = {325}
}

L. Devroye,
C. McDiarmid,
and B. Reed.
Giant components for two expanding graph processes.
In Mathematics and computer science, II (Versailles, 2002),
Trends Math.,
pages 161173.
Birkhäuser,
Basel,
2002.
@incollection{MR1940135,
AUTHOR = {Devroye, L. and McDiarmid, C. and Reed, B.},
TITLE = {Giant components for two expanding graph processes},
BOOKTITLE = {Mathematics and computer science, II (Versailles, 2002)},
SERIES = {Trends Math.},
PAGES = {161173},
PUBLISHER = {Birkh\"auser},
ADDRESS = {Basel},
YEAR = {2002},
}

A. Ferreira.
Parallel Computing: Models.
In C. Floudas and P. Pardalos, editors,Encyclopedia of Optimization.
Kluwer Academic Publisher, Boston (USA),
2002.
@INCOLLECTION{Fer02a,
AUTHOR = {A. Ferreira},
BOOKTITLE = {Encyclopedia of Optimization},
EDITOR = {C. Floudas and P. Pardalos},
PUBLISHER = {Kluwer Academic Publisher, Boston (USA)},
TITLE = {{Parallel Computing: Models}},
YEAR = {2002},
}

A. Ferreira,
J. Galtier,
and P. Penna.
Topological design, routing and handover in satellite networks.
In I. Stojmenovic, editor,Handbook of Wireless Networks and Mobile Computing,
pages 473507.
John Wiley and Sons,
2002.
[PDF
]
@INCOLLECTION{FGP02,
AUTHOR = {A. Ferreira and J. Galtier and P. Penna},
BOOKTITLE = {Handbook of Wireless Networks and Mobile Computing},
EDITOR = {I. Stojmenovic},
PAGES = {473507},
PUBLISHER = {John Wiley and Sons},
TITLE = {Topological design, routing and handover in satellite networks},
YEAR = {2002},
PDF = {ftp://ftpsop.inria.fr/mascotte/Publications/FGP02.pdf},
}

A. Ferreira and I. GuérinLassous.
Discrete Computing with Coarse Grained Systems.
In R. Corrêa,
I. Dutra,
M. Fiallos,
and F. Gomes, editors,Parallel and Distributed Algorithms: Theory, Algorithmic Techniques and Applications,
Applied Optimization,
chapter 5, part I,
pages 117143.
Kluwer Academic Publishers,
Boston (USA),
2002.
@INCOLLECTION{FeGu02,
AUTHOR = {A. Ferreira and I. Gu\'erinLassous},
BOOKTITLE = {Parallel and Distributed Algorithms: {T}heory, Algorithmic Techniques and Applications},
EDITOR = {R. Corr\^ea and I. Dutra and M. Fiallos and F. Gomes},
PUBLISHER = {Kluwer Academic Publishers},
TITLE = {Discrete Computing with Coarse Grained Systems},
year = {2002},
series = {Applied Optimization},
chapter = {5, part I},
address = {Boston (USA)},
pages = {117143},
}

B. Beauquier and E. Darrot.
On Arbitrary Size Waksman Networks and their Vulnerability.
Parallel Processing Letters,
12(3),
2002.
@ARTICLE{BeDa02,
AUTHOR = {B. Beauquier and E. Darrot},
JOURNAL = {Parallel Processing Letters},
VOLUME = {12},
NUMBER = {3},
PUBLISHER = {World Scientific},
TITLE = {On Arbitrary Size {W}aksman Networks and their Vulnerability},
YEAR = {2002},
}

J.C. Bermond,
E. Darrot,
and O. Delmas.
Design of fault tolerant onboard networks in satellites.
Networks,
40:202207,
2002.
[PDF
]
@Article{BDD02,
Author= {J.C. Bermond and E. Darrot and O. Delmas},
Title= {Design of fault tolerant onboard networks in satellites},
Year={2002},
Journal={Networks},
Volume= {40},
Pages={202207},
PDF={ftp://ftpsop.inria.fr/mascotte/personnel/JeanClaude.Bermond/PUBLIS/BDD02.pdf},
}

H.J. Böckenhauer,
J. Hromkovic,
R. Klasing,
S. Seibert,
and W. Unger.
Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem.
Theoretical Computer Science,
285(1):324,
2002.
@Article{BHK+02,
author = {H.J.~B\"ockenhauer and J.~Hromkovi\v{c} and R.~Klasing and S.~Seibert and W.~Unger},
title = {Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem},
journal = {Theoretical Computer Science},
year = {2002},
volume = {285},
number = {1},
pages = {324},
}

E. Caceres,
F. Dehne,
A. Ferreira,
P. Flocchini,
I. Rieping,
A. Roncato,
N. Santoro,
and S. Song.
Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP.
Algorithmica,
33:183200,
2002.
@ARTICLE{CDF+02,
AUTHOR = {E. Caceres and F. Dehne and A. Ferreira and P. Flocchini and I. Rieping and A. Roncato and N. Santoro and S. Song},
JOURNAL = {Algorithmica},
PAGES = {183200},
TITLE = {{Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP}},
VOLUME = {33},
YEAR = {2002},
}

H. Cirstea,
C. Kirchner,
and L. Liquori.
Rewriting Calculus with(out) Types.
WRLA, International Workshop on Rewriting Logic and its Applications. Electr. Notes Theor. Comput. Sci.,
71,
2002.
[POSTSCRIPT
]
@article{CKL02,
author = {H. Cirstea and C. Kirchner and L. Liquori},
title = {{Rewriting Calculus with(out) Types}},
journal = {WRLA, International Workshop on Rewriting Logic and its Applications. Electr. Notes Theor. Comput. Sci.},
volume = {71},
year = {2002},
POSTSCRIPT= {http://wwwsop.inria.fr/mascotte/Luigi.Liquori/PAPERS/wrla02.ps.gz}
}

C. Cooper,
A. Frieze,
and B. Reed.
Random regular graphs of nonconstant degree: connectivity and Hamiltonicity.
Combin. Probab. Comput.,
11(3):249261,
2002.
@article {MR1909501,
AUTHOR = {Cooper, C. and Frieze, A. and Reed, B.},
TITLE = {Random regular graphs of nonconstant degree: connectivity and {H}amiltonicity},
JOURNAL = {Combin. Probab. Comput.},
VOLUME = {11},
YEAR = {2002},
NUMBER = {3},
PAGES = {249261},
}

C. Cooper,
A. Frieze,
B. Reed,
and O. Riordan.
Random regular graphs of nonconstant degree: independence and chromatic number.
Combin. Probab. Comput.,
11(4):323341,
2002.
@article {MR1918719,
AUTHOR = {Cooper, C. and Frieze, A. and Reed, B. and Riordan, O.},
TITLE = {Random regular graphs of nonconstant degree: independence and chromatic number},
JOURNAL = {Combin. Probab. Comput.},
VOLUME = {11},
YEAR = {2002},
NUMBER = {4},
PAGES = {323341},
}

D. Coudert,
A. Ferreira,
and S. Pérennes.
Isomorphisms of the De Bruijn Digraph and FreeSpace Optical Networks.
Networks (WileyInterscience),
40(3):155164,
October 2002.
[PDF
] [POSTSCRIPT
]
Abstract: 
The de Bruijn digraph $B(d,D)$ has degree $d$, diameter $D$, $d^D$ vertices and $d^{D+1}$ arcs. It is usually defined by words of size $D$ on an alphabet of cardinality $d$, through a cyclic left shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an {\em arbitrary} permutation on the alphabet {\bf and} an {\em arbitrary} permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is {\em cyclic}. We use this result to improve from $O\left(d^{D+1}\right)$ to $\Theta\left(\sqrt{d^{D+1}}\right)$ the number of lenses required for the implementation of $B(d,D)$ by the Optical Transpose Interconnection System proposed by Marsden {\em et al.} (Optics Letters 18(13):10831085, July 1993). 
@ARTICLE{CFP02,
author = {D. Coudert and A. Ferreira and S. P\'erennes},
title = {Isomorphisms of the De Bruijn Digraph and FreeSpace Optical Networks},
journal = {Networks (WileyInterscience)},
year = {2002},
volume = {40},
pages = {155164},
number = {3},
month = oct,
abstract = {The de Bruijn digraph $B(d,D)$ has degree $d$, diameter $D$, $d^D$ vertices and $d^{D+1}$ arcs. It is usually defined by words of size $D$ on an alphabet of cardinality $d$, through a cyclic left shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an {\em arbitrary} permutation on the alphabet {\bf and} an {\em arbitrary} permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is {\em cyclic}. We use this result to improve from $O\left(d^{D+1}\right)$ to $\Theta\left(\sqrt{d^{D+1}}\right)$ the number of lenses required for the implementation of $B(d,D)$ by the Optical Transpose Interconnection System proposed by Marsden {\em et al.} (Optics Letters 18(13):10831085, July 1993).},
pdf = {ftp://ftpsop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFPNetworksac02.pdf},
postscript = {ftp://ftpsop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFPNetworksac02.ps.gz}
}

A. Ferreira,
I. GuérinLassous,
K. Marcus,
and A. RauChaplin.
Parallel Computation on Interval Graphs: Algorithms and Experiments.
Concurrency and Computation  Practice and Experience,
56(1):4770,
january 2002.
@ARTICLE{FGM+02,
AUTHOR = {A. Ferreira and I. Gu\'erinLassous and K. Marcus and A. RauChaplin},
JOURNAL = {Concurrency and Computation  Practice and Experience},
TITLE = {{Parallel Computation on Interval Graphs: Algorithms and Experiments}},
YEAR = {2002},
MONTH = {january},
NUMBER = {1},
PAGES = {4770},
VOLUME = {56},
}

F. Havet.
Trees in Tournament.
Discrete Mathematics,
243(13):121134,
2002.
[PDF
]
@ARTICLE{Hav02a,
AUTHOR = {F. Havet},
JOURNAL = {Discrete Mathematics},
NUMBER = {13},
PAGES = {121134},
TITLE = {Trees in Tournament},
VOLUME = {243},
YEAR = {2002},
PDF = {ftp://ftpsop.inria.fr/mascotte/Publications/Hav02a.pdf},
}

F. Havet and J. Zerovnik.
Finding a Five Bicolouring of a TriangleFree Subgraph of the Triangular Lattice.
Discrete Mathematics,
244:103108,
2002.
@ARTICLE{HaZe02,
AUTHOR = {F. Havet and J. Zerovnik},
JOURNAL = {Discrete Mathematics},
PAGES = {103108},
TITLE = {Finding a Five Bicolouring of a TriangleFree Subgraph of the Triangular Lattice},
VOLUME = {244},
YEAR = {2002},
}

B. Reed and B. Sudakov.
Asymptotically the list colouring constants are 1.
J. Combin. Theory Ser. B,
86(1):2737,
2002.
@article {MR1930121,
AUTHOR = {Reed, B. and Sudakov, B.},
TITLE = {Asymptotically the list colouring constants are 1},
JOURNAL = {J. Combin. Theory Ser. B},
VOLUME = {86},
YEAR = {2002},
NUMBER = {1},
PAGES = {2737},
}

E. Altman,
J. Galtier,
and C. Touati.
Fair power and transmission rate control in wireless networks.
In Proc. of IEEE GlobeCom'02,
Taipei, Taiwan,
November 2002.
@InProceedings{AGT02b,
author="E. Altman and J. Galtier and C. Touati",
title ="Fair power and transmission rate control in wireless networks",
booktitle = {Proc. of IEEE GlobeCom'02},
year = {2002},
address = {Taipei, Taiwan},
month =nov,
}

E. Altman,
J. Galtier,
and C. Touati.
SemiDefinite Programming Approach for Bandwidth Allocation and Routing in Networks.
In Proc. of 10th Int. Symp. on Dynamic Games and Application  Networking Games & Resource Allocation Workshop (NGRA2002),
Petrozavodsk, Russia,
July 2002.
Altman and Mazaloz.
@InProceedings{AGT02c,
author = {E. Altman and J. Galtier and C. Touati},
title = {SemiDefinite Programming Approach for Bandwidth Allocation and Routing in Networks},
booktitle = {Proc. of 10th Int. Symp. on Dynamic Games and Application  Networking Games \& Resource Allocation Workshop (NGRA2002)},
publisher = {Altman and Mazaloz},
year = 2002,
address = {Petrozavodsk, Russia},
month = jul
}

E. Altman,
J. Galtier,
and C. Touati.
Utility Based Fair Bandwidth Allocation.
In IASTED International Conference on Networks, Parallel and Distributed Processing, and Applications (NPDPA 2002),
2002.
@InProceedings{AGT02a,
author = {E. Altman and J. Galtier and C. Touati},
title = {Utility Based Fair Bandwidth Allocation},
booktitle = {IASTED International Conference on Networks, Parallel and Distributed Processing, and Applications (NPDPA 2002)},
year = 2002
}

J.C. Bermond,
S. Choplin,
and S. Pérennes.
Hierarchical Ring Network Design.
In 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO'02),
pages 116,
2002.
Carleton Scientific.
@INPROCEEDINGS{BCP02,
AUTHOR = {J.C. Bermond and S. Choplin and S. P\'erennes},
BOOKTITLE = {9th International Colloquium on Structural Information and Communication Complexity ({SIROCCO}'02)},
PAGES = {116},
PUBLISHER = {Carleton Scientific},
TITLE = {Hierarchical Ring Network Design},
YEAR = {2002},
}

H.J. Böckenhauer,
D. Bongartz,
J. Hromkovic,
R. Klasing,
G. Proietti,
S. Seibert,
and W. Unger.
On the hardness of constructing minimal 2connected spanning subgraphs in complete graphs with sharpened triangle inequality.
In Proc. of the 22nd Conference on Foundations of Software Technology and Theoretial Computer Science (FSTTCS 2002),
volume 2556 of Lecture Notes in Computer Science,
pages 5970,
2002.
SpringerVerlag.
@InProceedings{BBH+02,
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 the hardness of constructing minimal 2connected spanning subgraphs in complete graphs with sharpened triangle inequality},
booktitle = {Proc. of the 22nd Conference on Foundations of Software Technology and Theoretial Computer Science (FSTTCS 2002)},
series = {Lecture Notes in Computer Science},
publisher = {SpringerVerlag},
volume = {2556},
year = {2002},
isbn = {3540002251},
pages = {5970},
}

D. Coudert and H. Rivano.
Lightpath assignment for multifibers WDM networks with wavelength translators.
In Global Telecommunications Conference, 2002. GLOBECOM '02. IEEE,
volume 3,
pages 26862690vol.3,
1721 Nov. 2002.
Note: OPNT015.
[PDF
]
Abstract: 
We consider the problem of finding a lightpath assignment for a given set of communication requests on a multifiber WDM optical network with wavelength translators. Given such a network and w, the number of wavelengths available on each fiber, k, the number of fibers per link, and c, the number of partial wavelength translations available on each node, our problem stands for deciding whether it is possible to find a wlightpath for each request in the set such that there is no link carrying more that k lightpaths using the same wavelength nor node where more than c wavelength translations take place. Our main theoretical result is the writing of this problem as a particular instance of integral multicommodity flow, hence integrating routing and wavelength assignment in the same model. We then provide three heuristics mainly based upon randomized rounding of fractional multicommodity flow and enhancements that are three different answers to the tradeoff between efficiency and tightness of approximation, and discuss their practical performances on both theoretical and realworld instances. 
@INPROCEEDINGS{CoRi02b,
author = {Coudert, D. and Rivano, H.},
title = {Lightpath assignment for multifibers WDM networks with wavelength translators},
booktitle = {Global Telecommunications Conference, 2002. GLOBECOM '02. IEEE},
year = {2002},
volume = {3},
pages = {26862690vol.3},
month = {1721 Nov.},
note = {OPNT015},
abstract = {We consider the problem of finding a lightpath assignment for a given set of communication requests on a multifiber WDM optical network with wavelength translators. Given such a network and w, the number of wavelengths available on each fiber, k, the number of fibers per link, and c, the number of partial wavelength translations available on each node, our problem stands for deciding whether it is possible to find a wlightpath for each request in the set such that there is no link carrying more that k lightpaths using the same wavelength nor node where more than c wavelength translations take place. Our main theoretical result is the writing of this problem as a particular instance of integral multicommodity flow, hence integrating routing and wavelength assignment in the same model. We then provide three heuristics mainly based upon randomized rounding of fractional multicommodity flow and enhancements that are three different answers to the tradeoff between efficiency and tightness of approximation, and discuss their practical performances on both theoretical and realworld instances.},
pdf = {ftp://ftpsop.inria.fr/mascotte/personnel/David.Coudert/Publication/CRGlobecom02.pdf}
}

D. Coudert and H. Rivano.
Routage optique dans les réseaux WDM multifibres avec conversion partielle..
In AlgoTel'02,
Mèze, France,
pages 1724,
May 2002.
[WWW
] [PDF
] [POSTSCRIPT
]
Abstract: 
Nous consid\'erons le probl\`eme du routage optique d'un ensemble donn\'e de requ\^etes de communications dans un r\'eseau \wdm multifibres avec conversion partielle. \'Etant donn\'e un tel r\'eseau disposant de $w$ longueurs d'onde par fibre, $k$ fibres par lien et $c$ conversions possibles par \noeud du r\'eseau, le probl\`eme revient \`a d\'ecider s'il est possible de trouver un chemin $w$color\'e pour chaque requ\^ete, de sorte qu'au plus $k$ chemins utilisent une m\^eme longueur d'onde sur un m\^eme lien du r\'eseau et qu'aucun \noeud n'op\`ere plus de $c$ conversions. Notre r\'esultat principal r\'eside dans l'\'ecriture de ce probl\`eme sous la forme d'une instance particuli\`ere de multiflot entier, int\'egrant dans un m\^eme mod\`ele le routage et l'affectation de longueurs d'onde. Nous fournissons ensuite trois heuristiques bas\'ees sur l'arrondi al\'eatoire de multiflots fractionnaires, qui sont trois r\'eponses diff\'erentes au compromis efficacit\'e/pr\'ecision des approximations. Nous les validons en comparant leur performances sur des instances th\'eoriques ou issue du monde r\'eel. 
@INPROCEEDINGS{CoRi02,
author = {D. Coudert and H. Rivano},
title = {Routage optique dans les r\'eseaux {WDM} multifibres avec conversion partielle.},
booktitle = {AlgoTel'02},
year = {2002},
pages = {1724},
address = {M\`eze, France},
month = may,
abstract = {Nous consid\'erons le probl\`eme du routage optique d'un ensemble donn\'e de requ\^etes de communications dans un r\'eseau \wdm multifibres avec conversion partielle. \'Etant donn\'e un tel r\'eseau disposant de $w$ longueurs d'onde par fibre, $k$ fibres par lien et $c$ conversions possibles par \noeud du r\'eseau, le probl\`eme revient \`a d\'ecider s'il est possible de trouver un chemin $w$color\'e pour chaque requ\^ete, de sorte qu'au plus $k$ chemins utilisent une m\^eme longueur d'onde sur un m\^eme lien du r\'eseau et qu'aucun \noeud n'op\`ere plus de $c$ conversions. Notre r\'esultat principal r\'eside dans l'\'ecriture de ce probl\`eme sous la forme d'une instance particuli\`ere de multiflot entier, int\'egrant dans un m\^eme mod\`ele le routage et l'affectation de longueurs d'onde. Nous fournissons ensuite trois heuristiques bas\'ees sur l'arrondi al\'eatoire de multiflots fractionnaires, qui sont trois r\'eponses diff\'erentes au compromis efficacit\'e/pr\'ecision des approximations. Nous les validons en comparant leur performances sur des instances th\'eoriques ou issue du monde r\'eel.},
pdf = {ftp://ftpsop.inria.fr/mascotte/personnel/David.Coudert/Publication/CRAlgoTel02.pdf},
postscript = {ftp://ftpsop.inria.fr/mascotte/personnel/David.Coudert/Publication/CRAlgoTel02.ps.gz},
url = {http://hipercom.inria.fr/algotel2002/}
}

A. Ferreira.
On models and algorithms for dynamic communication networks: The case for evolving graphs.
In 4$^{\rm e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2002),
Mèze, France,
May 2002.
@INPROCEEDINGS{Fer02b,
AUTHOR = {A. Ferreira},
ADDRESS = {Mèze, France},
BOOKTITLE = {4$^{\rm e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2002)},
MONTH = may,
TITLE = {{{On models and algorithms for dynamic communication networks: The case for evolving graphs}}},
YEAR = {2002},
}

A. Ferreira,
S. Pérennes,
A. Richa,
H. Rivano,
and N. Stier.
On the design of multifiber WDM networks.
In AlgoTel'02,
Mèze, France,
pages 2532,
May 2002.
[WWW
] [PDF
] [POSTSCRIPT
]
Abstract: 
In this paper, we address 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 wellknown 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 \emph{ conflict hypergraphs}. Conflict hypergraphs accurately capture the lightpath interdependencies, generalizing the conflict graphs used for singlefiber networks. By relating the $(k,w)$\wap with the hypergraph coloring problem, we prove that the former is \npc, 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 an integer programming formulation, and the second consists of a heuristic based on a randomized algorithm. 
@INPROCEEDINGS{FPR+02,
author = {A. Ferreira and S. Pérennes and A. Richa and H. Rivano and N. Stier},
title = {On the design of multifiber WDM networks},
booktitle = {AlgoTel'02},
year = {2002},
pages = {2532},
address = {Mèze, France},
month = {May},
abstract = {In this paper, we address 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 wellknown 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 \emph{ conflict hypergraphs}. Conflict hypergraphs accurately capture the lightpath interdependencies, generalizing the conflict graphs used for singlefiber networks. By relating the $(k,w)$\wap with the hypergraph coloring problem, we prove that the former is \npc, 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 an integer programming formulation, and the second consists of a heuristic based on a randomized algorithm.},
pdf = {ftp://ftpsop.inria.fr/mascotte/Herve.Rivano/Biblio/fprrs02.pdf},
postscript = {ftp://ftpsop.inria.fr/mascotte/Herve.Rivano/Biblio/fprrs02.ps.gz},
url = {http://hipercom.inria.fr/algotel2002/}
}

F. Havet.
Design of Fault Tolerant Satellite Networks with Priorities via Selectors.
In Proc. of SIROCCO'02,
Andros, Greece,
pages 165180,
June 2002.
@INPROCEEDINGS{Hav02b,
AUTHOR = {F. Havet},
ADDRESS = {Andros, Greece},
BOOKTITLE = {Proc. of SIROCCO'02},
MONTH = jun,
PAGES = {165180},
TITLE = {Design of Fault Tolerant Satellite Networks with Priorities via Selectors},
YEAR = {2002},
}

F. Havet.
Robustness of a Routing Tree for the Push Tree Problem.
In $4^{e}$ rencontres francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'02),
Mèze, France,
pages 8186,
May 2002.
@INPROCEEDINGS{Hav02c,
AUTHOR = {F. Havet},
ADDRESS = {Mèze, France},
BOOKTITLE = {$4^{e}$ rencontres francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'02)},
MONTH = may,
PAGES = {8186},
TITLE = {Robustness of a Routing Tree for the Push Tree Problem},
YEAR = {2002},
}

G. Huiban,
S. Pérennes,
and M. Syska.
Traffic Grooming in WDM Networks with MultiLayer Switches.
In IEEE ICC,
NewYork,
April 2002.
Note: CDRom.
@INPROCEEDINGS{HuPeSy02,
AUTHOR = {G. Huiban and S. P\'erennes and M. Syska},
ADDRESS = {NewYork},
BOOKTITLE = {IEEE ICC},
MONTH = apr,
TITLE = {Traffic Grooming in {WDM} Networks with MultiLayer Switches},
YEAR = {2002},
NOTE = {CDRom},
}

A. Jarry.
Disjoint Paths in Symmetric Digraphs.
In International Colloquium on Structural Information and Communi cation Complexity  SIROCCO,
Andros, Greece,
pages 211222,
June 2002.
Carleton.
@InProceedings{Jar02a,
author = {A. Jarry},
title = {{Disjoint Paths in Symmetric Digraphs}},
booktitle = {International Colloquium on Structural Information and Communi cation Complexity  SIROCCO},
pages = {211222},
year = {2002},
address = {Andros, Greece},
month = jun,
publisher = {Carleton},
}

P. Mussi.
Tuning Car Following Algorithms for Realistic Behaviour.
In AI, Simulation & Planning in High Autonomy Systems,
Lisbon, Portugal,
pages 281284,
April 2002.
@INPROCEEDINGS{Mus02,
AUTHOR = {P. Mussi},
ADDRESS = {Lisbon, Portugal},
BOOKTITLE = {AI, Simulation \& Planning in High Autonomy Systems},
MONTH = {April},
TITLE = {Tuning Car Following Algorithms for Realistic Behaviour},
YEAR = {2002},
pages={281284},
}

B. Reed and B. Sudakov.
List colouring of graphs with at most $(2o(1))\chi$ vertices.
In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002),
Beijing,
pages 587603,
2002.
Higher Ed. Press.
@inproceedings{MR1957563,
AUTHOR = {Reed, B. and Sudakov, B.},
TITLE = {List colouring of graphs with at most {$(2o(1))\chi$} vertices},
BOOKTITLE = {Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002)},
PAGES = {587603},
PUBLISHER = {Higher Ed. Press},
ADDRESS = {Beijing},
YEAR = {2002},
}

E. Altman,
J. Galtier,
and C. Touati.
Fair Bandwidth allocation between service providers in a geostationary satellite network.
Technical report RR4421,
INRIA,
March 2002.
@TechReport{AGT02c,
author = {E. Altman and J. Galtier and C. Touati},
title = {Fair Bandwidth allocation between service providers in a geostationary satellite network },
institution = {INRIA},
year = 2002,
number = {RR4421},
month = mar
}

N. Baskiotis,
S. Pérennes,
and H. Rivano.
Heuristic design of multifiber WDM optical networks by randomized rounding of multicommodity flow.
Research Report RR4418,
INRIA Research Report 4418,
2002.
[WWW
]
Abstract: 
Ces travaux s'attachent à définir le problème du routage optique multifibres ainsi qu'une modélisation en terme de multiflot entier. Cette modélisation permet d'envisager de bonnes approximations et heuristiques. 
@TECHREPORT{BPR02,
author = {N. Baskiotis and S. Pérennes and H. Rivano},
title = {Heuristic design of multifiber WDM optical networks by randomized rounding of multicommodity flow},
institution = {INRIA Research Report 4418},
year = {2002},
type = {Research Report},
number = {RR4418},
abstract = {Ces travaux s'attachent à définir le problème du routage optique multifibres ainsi qu'une modélisation en terme de multiflot entier. Cette modélisation permet d'envisager de bonnes approximations et heuristiques.},
url = {http://hal.inria.fr/inria00072170}
}

B. Beauquier,
S. Pérennes,
and M. Syska.
Efficient Access to Optical Bandwidth, Routing and Grooming in WDM Networks: Stateoftheart survey.
IST CRESCCO report,
Projet MASCOTTE (CNRS/INRIA/UNSA),
Sophia Antipolis,
July 2002.
@TECHREPORT{CRE02,
AUTHOR = {B. Beauquier and S. P\'erennes and M. Syska},
ADDRESS = {Sophia Antipolis},
INSTITUTION = {Projet MASCOTTE (CNRS/INRIA/UNSA)},
MONTH = jul,
TITLE = {Efficient Access to Optical Bandwidth, Routing and Grooming in {WDM} Networks: {S}tateoftheart survey},
TYPE = {{IST} {CRESCCO} report},
YEAR = {2002},
}

J.C. Bermond and S. Céroi.
Minimizing SONET ADMs in unidirectional WDM ring with grooming ratio 3.
Technical report RR4626,
INRIA,
Sophia Antipolis,
November 2002.
@Techreport{BeCe02,
author = {J.C. Bermond and S. Céroi},
title = {Minimizing {SONET ADM}s in unidirectional {WDM} ring with grooming ratio 3},
institution = {INRIA},
year = {2002},
number = {RR4626},
address = {Sophia Antipolis},
month = nov,
}

S. Bessy,
F. Havet,
and J. Palaysi.
Pancyclic Arcs and Connectivity in Tournaments.
Rapport de recherche INRIA/RR4522,
Projet MASCOTTE,
Sophia Antipolis,
August 2002.
@TECHREPORT{BHP02,
AUTHOR = {S. Bessy and F. Havet and J. Palaysi},
ADDRESS = {Sophia Antipolis},
INSTITUTION = {Projet MASCOTTE},
MONTH = aug,
TITLE = {Pancyclic Arcs and Connectivity in Tournaments},
TYPE = {{R}apport de recherche {INRIA/RR4522}},
YEAR = {2002},
}

S. Bhadra and A. Ferreira.
Computing multicast trees in dynamic networks using evolving graphs.
Research Report 4531,
INRIA,
2002.
@TECHREPORT{BhFe02,
AUTHOR = {S. Bhadra and A. Ferreira},
INSTITUTION = {INRIA},
NUMBER = {4531},
TITLE = {Computing multicast trees in dynamic networks using evolving graphs},
TYPE = {Research Report},
YEAR = {2002},
}

D. Coudert and H. Rivano.
Lightpath assignment for multifibers WDM optical networks with wavelength translators.
Research Report,
INRIA Research Report 4487,
2002.
[WWW
] [PDF
]
Abstract: 
We consider the problem of finding a lightpath assignment for a given set of communication requests on a multifiber WDM optical network with wavelength translators. Given such a network, and w the number of wavelengths available on each fiber, k the number of fiber per link and c the number of partial wavelength translation available on each node, our problem stands for deciding whether it is possible to find a wlightpath for each request in the set such that there is no link carrying more that k lightpaths using the same wavelength nor node where more than c wavelength translations take place. Our main theoretical result is the writing of this problem as a particular instance of integral multicommodity flow, hence integrating routing and wavelength assignment in the same model. We then provide three heuristics mainly based upon randomized rounding of fractional multicommodity flow and enhancements that are three different answers to the tradeoff between efficiency and tightness of approximation and discuss their practical performances on both theoretical and realworld instances. 
@TECHREPORT{CoRi02c,
author = {D. Coudert and H. Rivano},
title = {Lightpath assignment for multifibers WDM optical networks with wavelength translators},
institution = {INRIA Research Report 4487},
year = {2002},
type = {Research Report},
abstract = {We consider the problem of finding a lightpath assignment for a given set of communication requests on a multifiber WDM optical network with wavelength translators. Given such a network, and w the number of wavelengths available on each fiber, k the number of fiber per link and c the number of partial wavelength translation available on each node, our problem stands for deciding whether it is possible to find a wlightpath for each request in the set such that there is no link carrying more that k lightpaths using the same wavelength nor node where more than c wavelength translations take place. Our main theoretical result is the writing of this problem as a particular instance of integral multicommodity flow, hence integrating routing and wavelength assignment in the same model. We then provide three heuristics mainly based upon randomized rounding of fractional multicommodity flow and enhancements that are three different answers to the tradeoff between efficiency and tightness of approximation and discuss their practical performances on both theoretical and realworld instances.},
url = {http://hal.inria.fr/inria00072101},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/07/21/01/PDF/RR4487.pdf&docid=72101},
}

A. Ferreira and L. Viennot.
A Note on Models, Algorithms, and Data Structures for Dynamic Communication Networks.
Research Report 4403,
INRIA,
2002.
@TECHREPORT{FeVi02,
AUTHOR = {A. Ferreira and L. Viennot},
INSTITUTION = {INRIA},
NUMBER = {4403},
TITLE = {A Note on Models, Algorithms, and Data Structures for Dynamic Communication Networks},
TYPE = {Research Report},
YEAR = {2002},
}

F. Giroire,
A. Nucci,
N. Taft,
and C. Diot.
Increasing the Robustness of IP Backbones in the Absence of Optical Level Protection.
Technical Report,
Sprint,
2002.
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. 
@techreport{GNTD02,
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},
institution = {Sprint},
type = {Technical Report},
year = {2002},
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.},
}

F. Havet.
Pancyclic Arcs and Connectivity in Tournaments.
Rapport de recherche INRIA/RR4378,
Projet MASCOTTE,
Sophia Antipolis,
March 2002.
@TECHREPORT{Hav02d,
AUTHOR = {F. Havet},
ADDRESS = {Sophia Antipolis},
INSTITUTION = {Projet MASCOTTE},
MONTH = mar,
TITLE = {Pancyclic Arcs and Connectivity in Tournaments},
TYPE = {{R}apport de recherche {INRIA/RR4378}},
YEAR = {2002},
}

F. Havet and J. Yu.
On $(d,1)$total labelling of graphs.
Rapport de recherche INRIA,
Projet MASCOTTE,
Sophia Antipolis,
November 2002.
@TECHREPORT{HaYu02,
AUTHOR = {F. Havet and J. Yu},
ADDRESS = {Sophia Antipolis},
INSTITUTION = {Projet MASCOTTE},
MONTH = nov,
TITLE = {On $(d,1)$total labelling of graphs},
TYPE = {{R}apport de recherche {INRIA}},
YEAR = {2002},
}

A. Jarry.
Integral Symmetric 2Commodity Flows.
Technical report RR4622,
INRIA,
Sophia Antipolis,
November 2002.
@TechReport{Jar02b,
author = {A. Jarry},
title = {Integral Symmetric 2Commodity Flows},
institution = {INRIA},
year = {2002},
number = {RR4622},
address = {Sophia Antipolis},
month = nov,
}

A. Jarry and A. Laugier.
Twoconnected graphs with given diameter.
Technical report RR4307,
INRIA,
Sophia Antipolis,
March 2002.
@TechReport{JaLa02,
author = {A. Jarry and A. Laugier},
title = {Twoconnected graphs with given diameter},
institution = {INRIA},
year = {2002},
number = {RR4307},
address = {Sophia Antipolis},
month = mar,
}

B. Xuan,
A. Ferreira,
and A. Jarry.
Computing shortest, fastest, and foremost journeys in dynamic networks.
Technical report RR4589,
INRIA,
Sophia Antipolis,
November 2002.
@TechReport{BFJ02,
author = {B. Xuan and A. Ferreira and A. Jarry},
title = {Computing shortest, fastest, and foremost journeys in dynamic networks},
institution = {INRIA},
year = {2002},
number = {RR4589},
address = {Sophia Antipolis},
month = nov,
}

M. Syska.
PORTO: Planification et Optimisation des Réseaux de Transport Optiques.
Poster, Colloque annuel du RNRT, Grenoble, 7 février,
2002.
[WWW
]
@misc{Sys02,
author = {M. Syska},
title = {{PORTO}: Planification et Optimisation des Réseaux de Transport Optiques},
howpublished = {Poster, Colloque annuel du {RNRT}, Grenoble, 7 février},
url = {http://www.telecom.gouv.fr/rnrt/coll/posters/porto.ppt},
year = {2002}
}

B. M. B. Xuan.
Graphes évolutifs et réseaux dynamiques à calendrier fixé,
2002.
@MISC{Bui02,
AUTHOR = {B. M. B. Xuan},
SCHOOL = {ENS Lyon},
TITLE = {Graphes évolutifs et réseaux dynamiques à calendrier fixé},
TYPE = {Rapport de stage},
YEAR = {2002},
}

O. Françoise.
Conception d'une API de contrôle générique pour le noyau Linux basée sur le mécanisme de système de fichiers virtuels.
Rapport de stage de DEA,
ESSI,
June 2002.
@MASTERSTHESIS{Fra02a,
AUTHOR = {O. Fran\c coise},
MONTH = {jun},
SCHOOL = {ESSI},
TITLE = {Conception d'une {API} de contr\^ole g\'en\'erique pour le noyau {L}inux bas\'ee sur le m\'ecanisme de syst\`eme de fichiers virtuels},
TYPE = {{R}apport de stage de DEA},
YEAR = {2002},
}

J.C. Godin.
Choisissabilité de graphes et allocations de fréquences.
Rapport de DEA MDFI,
Université de Luminy, Marseille,
2002.
@MASTERSTHESIS{God02,
AUTHOR = {J.C. Godin},
SCHOOL = {Universit\'e de Luminy, Marseille},
TITLE = {Choisissabilité de graphes et allocations de fréquences},
type = {Rapport de DEA MDFI},
YEAR = {2002},
}

T. Guillier.
Implantation au niveau utilisateur du protocole de contrôle de MPCFS.
Rapport de stage, 2e année d'Ingénieur,
ESSI,
2002.
@MASTERSTHESIS{Gui02,
AUTHOR = {T. Guillier},
SCHOOL = {ESSI},
TITLE = {Implantation au niveau utilisateur du protocole de contr\^ole de {MPCFS}},
TYPE = {{R}apport de stage, 2e ann\'ee d'Ing\'enieur},
YEAR = {2002},
}

B. Lévèque.
Minimisation du nombre d'ADM dans les réseaux WDM.
Rapport de stage,
ENS Lyon, Licence d'Informatique,
2002.
@MASTERSTHESIS{Lev02,
AUTHOR = {B. L\'ev\`eque},
SCHOOL = {ENS Lyon, Licence d'Informatique},
TITLE = {Minimisation du nombre d'{ADM} dans les r\'eseaux {WDM}},
TYPE = {{R}apport de stage},
YEAR = {2002},
}

P. Pons.
Recherche d'algorithmes pour évaluer la disponibilité d'un réseau de télécommunications.
Rapport de DEA,
September 2002.
@MastersThesis{Pons02,
author = {P. Pons},
title = {Recherche d'algorithmes pour \'evaluer la disponibilit\'e d'un r\'eseau de t\'el\'ecommunications},
type = {Rapport de DEA},
month = {sep},
year = {2002}
}

S. Rai.
Design and optimization of WDM networks: Grooming.
Rapport de stage,
IIT New Delhi,
2002.
@MASTERSTHESIS{Rai02,
AUTHOR = {S. Rai},
SCHOOL = {IIT New Delhi},
TITLE = {Design and optimization of {WDM} networks: Grooming},
type = {Rapport de stage},
YEAR = {2002}
}

F. Viger.
Modélisation de phénomènes complexes du trafic routier.
Rapport de Maîtrise d'Informatique,
ENS,
2002.
@MASTERSTHESIS{Vig02,
AUTHOR = {F. Viger},
SCHOOL = {ENS},
TITLE = {Mod\'elisation de ph\'enom\`enes complexes du trafic routier},
type = {{R}apport de Ma\^{i}trise d'Informatique},
YEAR = {2002},
}

R. Vuillemot.
Conception d'un modèle du protocole GMPLS pour l'environnement de simulation ASIMUT.
Rapport de Licence d'Informatique,
ENS Lyon,
2002.
@MASTERSTHESIS{Vui02,
AUTHOR = {R. Vuillemot},
SCHOOL = {ENS Lyon},
TITLE = {Conception d'un mod\`ele du protocole {GMPLS} pour l'environnement de simulation {ASIMUT}},
type = {{R}apport de Licence d'Informatique},
YEAR = {2002},
}

M. Walter.
Evaluation et validation d'un logiciel de dimensionnement de réseaux.
Rapport de DESS,
ESSI,
2002.
@MASTERSTHESIS{Wal02,
AUTHOR = {M. Walter},
SCHOOL = {ESSI},
TITLE = {Evaluation et validation d'un logiciel de dimensionnement de r\'eseaux},
type = {Rapport de DESS},
YEAR = {2002},
}

O. de Rivoyre.
Le Groupage par Tubes.
Rapport de stage, 3e année d'Ingénieur,
ESSI,
September 2002.
@MASTERSTHESIS{Riv02,
AUTHOR = {O. de Rivoyre},
MONTH = sep,
SCHOOL = {ESSI},
TITLE = {Le Groupage par Tubes},
type = {{R}apport de stage, 3e ann\'ee d'Ing\'enieur},
YEAR = {2002},
}
BACK TO MASCOTTE PUBLICATION INDEX
Last modified: Thu Oct 10 14:10:00 2013
This document was translated from BibT_{E}X by
bibtex2html
