-
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 3--25.
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 = {3--25}
}
-
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 161--173.
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 = {161--173},
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 hand-over in satellite networks.
In I. Stojmenovic, editor,Handbook of Wireless Networks and Mobile Computing,
pages 473--507.
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 = {473--507},
PUBLISHER = {John Wiley and Sons},
TITLE = {Topological design, routing and hand-over in satellite networks},
YEAR = {2002},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/FGP02.pdf},
}
-
A. Ferreira and I. Guérin-Lassous.
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 117--143.
Kluwer Academic Publishers,
Boston (USA),
2002.
@INCOLLECTION{FeGu02,
AUTHOR = {A. Ferreira and I. Gu\'erin-Lassous},
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 = {117--143},
}
-
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 on-board networks in satellites.
Networks,
40:202--207,
2002.
[PDF
]
@Article{BDD02,
Author= {J.-C. Bermond and E. Darrot and O. Delmas},
Title= {Design of fault tolerant on-board networks in satellites},
Year={2002},
Journal={Networks},
Volume= {40},
Pages={202--207},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Claude.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):3--24,
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 = {3--24},
}
-
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:183--200,
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 = {183--200},
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://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/wrla-02.ps.gz}
}
-
C. Cooper,
A. Frieze,
and B. Reed.
Random regular graphs of non-constant degree: connectivity and Hamiltonicity.
Combin. Probab. Comput.,
11(3):249--261,
2002.
@article {MR1909501,
AUTHOR = {Cooper, C. and Frieze, A. and Reed, B.},
TITLE = {Random regular graphs of non-constant degree: connectivity and {H}amiltonicity},
JOURNAL = {Combin. Probab. Comput.},
VOLUME = {11},
YEAR = {2002},
NUMBER = {3},
PAGES = {249--261},
}
-
C. Cooper,
A. Frieze,
B. Reed,
and O. Riordan.
Random regular graphs of non-constant degree: independence and chromatic number.
Combin. Probab. Comput.,
11(4):323--341,
2002.
@article {MR1918719,
AUTHOR = {Cooper, C. and Frieze, A. and Reed, B. and Riordan, O.},
TITLE = {Random regular graphs of non-constant degree: independence and chromatic number},
JOURNAL = {Combin. Probab. Comput.},
VOLUME = {11},
YEAR = {2002},
NUMBER = {4},
PAGES = {323--341},
}
-
D. Coudert,
A. Ferreira,
and S. Pérennes.
Isomorphisms of the De Bruijn Digraph and Free-Space Optical Networks.
Networks (Wiley-Interscience),
40(3):155-164,
October 2002.
[PDF
] [POSTSCRIPT
]
| Abstract: |
The de Bruijn digraph $B(d,D)$ has degree $d$, diameter $D$, $d^D$ vertices and $d^{D+1}$ arcs. It is usually defined by words of size $D$ on an alphabet of cardinality $d$, through a cyclic left shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an {\em arbitrary} permutation on the alphabet {\bf and} an {\em arbitrary} permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is {\em cyclic}. We use this result to improve from $O\left(d^{D+1}\right)$ to $\Theta\left(\sqrt{d^{D+1}}\right)$ the number of lenses required for the implementation of $B(d,D)$ by the Optical Transpose Interconnection System proposed by Marsden {\em et al.} (Optics Letters 18(13):1083-1085, July 1993). |
@ARTICLE{CFP02,
author = {D. Coudert and A. Ferreira and S. P\'erennes},
title = {Isomorphisms of the De Bruijn Digraph and Free-Space Optical Networks},
journal = {Networks (Wiley-Interscience)},
year = {2002},
volume = {40},
pages = {155-164},
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):1083-1085, July 1993).},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFP-Networks-ac02.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CFP-Networks-ac02.ps.gz}
}
-
A. Ferreira,
I. Guérin-Lassous,
K. Marcus,
and A. Rau-Chaplin.
Parallel Computation on Interval Graphs: Algorithms and Experiments.
Concurrency and Computation - Practice and Experience,
56(1):47--70,
january 2002.
@ARTICLE{FGM+02,
AUTHOR = {A. Ferreira and I. Gu\'erin-Lassous and K. Marcus and A. Rau-Chaplin},
JOURNAL = {Concurrency and Computation - Practice and Experience},
TITLE = {{Parallel Computation on Interval Graphs: Algorithms and Experiments}},
YEAR = {2002},
MONTH = {january},
NUMBER = {1},
PAGES = {47--70},
VOLUME = {56},
}
-
F. Havet.
Trees in Tournament.
Discrete Mathematics,
243(1--3):121--134,
2002.
[PDF
]
@ARTICLE{Hav02a,
AUTHOR = {F. Havet},
JOURNAL = {Discrete Mathematics},
NUMBER = {1--3},
PAGES = {121--134},
TITLE = {Trees in Tournament},
VOLUME = {243},
YEAR = {2002},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/Hav02a.pdf},
}
-
F. Havet and J. Zerovnik.
Finding a Five Bicolouring of a Triangle-Free Subgraph of the Triangular Lattice.
Discrete Mathematics,
244:103--108,
2002.
@ARTICLE{HaZe02,
AUTHOR = {F. Havet and J. Zerovnik},
JOURNAL = {Discrete Mathematics},
PAGES = {103--108},
TITLE = {Finding a Five Bicolouring of a Triangle-Free 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):27--37,
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 = {27--37},
}
-
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.
Semi-Definite 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 (NGRA-2002),
Petrozavodsk, Russia,
July 2002.
Altman and Mazaloz.
@InProceedings{AGT02c,
author = {E. Altman and J. Galtier and C. Touati},
title = {Semi-Definite 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 (NGRA-2002)},
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 1--16,
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 = {1--16},
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 2-connected 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 59--70,
2002.
Springer-Verlag.
@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 2-connected 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 = {Springer-Verlag},
volume = {2556},
year = {2002},
isbn = {3-540-00225-1},
pages = {59--70},
}
-
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 2686--2690vol.3,
17-21 Nov. 2002.
Note: OPNT-01-5.
[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 w-lightpath 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 trade-off between efficiency and tightness of approximation, and discuss their practical performances on both theoretical and real-world 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 = {2686--2690vol.3},
month = {17-21 Nov.},
note = {OPNT-01-5},
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 w-lightpath 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 trade-off between efficiency and tightness of approximation, and discuss their practical performances on both theoretical and real-world instances.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CR-Globecom02.pdf}
}
-
D. Coudert and H. Rivano.
Routage optique dans les réseaux WDM multifibres avec conversion partielle..
In AlgoTel'02,
Mèze, France,
pages 17-24,
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 = {17-24},
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://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CR-AlgoTel02.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CR-AlgoTel02.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 25--32,
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 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 \emph{ conflict hypergraphs}. Conflict hypergraphs 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 \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 = {25--32},
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 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 \emph{ conflict hypergraphs}. Conflict hypergraphs 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 \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://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/fprrs02.pdf},
postscript = {ftp://ftp-sop.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 165--180,
June 2002.
@INPROCEEDINGS{Hav02b,
AUTHOR = {F. Havet},
ADDRESS = {Andros, Greece},
BOOKTITLE = {Proc. of SIROCCO'02},
MONTH = jun,
PAGES = {165--180},
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 81--86,
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 = {81--86},
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 Multi-Layer Switches.
In IEEE ICC,
New-York,
April 2002.
Note: CD-Rom.
@INPROCEEDINGS{HuPeSy02,
AUTHOR = {G. Huiban and S. P\'erennes and M. Syska},
ADDRESS = {New-York},
BOOKTITLE = {IEEE ICC},
MONTH = apr,
TITLE = {Traffic Grooming in {WDM} Networks with Multi-Layer Switches},
YEAR = {2002},
NOTE = {CD-Rom},
}
-
A. Jarry.
Disjoint Paths in Symmetric Digraphs.
In International Colloquium on Structural Information and Communi cation Complexity -- SIROCCO,
Andros, Greece,
pages 211--222,
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 = {211--222},
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 281--284,
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={281--284},
}
-
B. Reed and B. Sudakov.
List colouring of graphs with at most $(2-o(1))\chi$ vertices.
In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002),
Beijing,
pages 587--603,
2002.
Higher Ed. Press.
@inproceedings{MR1957563,
AUTHOR = {Reed, B. and Sudakov, B.},
TITLE = {List colouring of graphs with at most {$(2-o(1))\chi$} vertices},
BOOKTITLE = {Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002)},
PAGES = {587--603},
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 RR-4421,
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 = {RR-4421},
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 RR-4418,
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 = {RR-4418},
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/inria-00072170}
}
-
B. Beauquier,
S. Pérennes,
and M. Syska.
Efficient Access to Optical Bandwidth, Routing and Grooming in WDM Networks: State-of-the-art survey.
IST CRESCCO report,
Projet MASCOTTE (CNRS/INRIA/UNSA),
Sophia Antipolis,
July 2002.
@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}tate-of-the-art 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 RR-4626,
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 = {RR-4626},
address = {Sophia Antipolis},
month = nov,
}
-
S. Bessy,
F. Havet,
and J. Palaysi.
Pancyclic Arcs and Connectivity in Tournaments.
Rapport de recherche INRIA/RR-4522,
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/RR-4522}},
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 w-lightpath 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 trade-off between efficiency and tightness of approximation and discuss their practical performances on both theoretical and real-world 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 w-lightpath 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 trade-off between efficiency and tightness of approximation and discuss their practical performances on both theoretical and real-world instances.},
url = {http://hal.inria.fr/inria-00072101},
pdf = {http://hal.inria.fr/action/open_file.php?url=http://hal.inria.fr/docs/00/07/21/01/PDF/RR-4487.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/RR-4378,
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/RR-4378}},
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 2-Commodity Flows.
Technical report RR-4622,
INRIA,
Sophia Antipolis,
November 2002.
@TechReport{Jar02b,
author = {A. Jarry},
title = {Integral Symmetric 2-Commodity Flows},
institution = {INRIA},
year = {2002},
number = {RR-4622},
address = {Sophia Antipolis},
month = nov,
}
-
A. Jarry and A. Laugier.
Two-connected graphs with given diameter.
Technical report RR-4307,
INRIA,
Sophia Antipolis,
March 2002.
@TechReport{JaLa02,
author = {A. Jarry and A. Laugier},
title = {Two-connected graphs with given diameter},
institution = {INRIA},
year = {2002},
number = {RR-4307},
address = {Sophia Antipolis},
month = mar,
}
-
B. Xuan,
A. Ferreira,
and A. Jarry.
Computing shortest, fastest, and foremost journeys in dynamic networks.
Technical report RR-4589,
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 = {RR-4589},
address = {Sophia Antipolis},
month = nov,
}
-
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},
}