Publications of year 2001

BACK TO COATI PUBLICATION INDEX

Publications of year 2001

Books and proceedings
  1. A. Ferreira and D. Krob, editors. Mobile Networks & Applications (MONET) -- Special Issue on Discrete Algorithms and Methods for Mobile Computing and Communications. ACM/Baltzer, 2001. 
    @BOOK{FeKr01,
EDITOR = {A. Ferreira and D. Krob},
PUBLISHER = {ACM/Baltzer},
TITLE = {{Mobile Networks \& Applications (MONET) -- Special Issue on Discrete Algorithms and Methods for Mobile Computing and Communications}},
YEAR = {2001},

}

     
  2. J. L. Ramìrez Alfonsìn and B. Reed, editors. Perfect graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Ltd., Chichester, 2001. 
    @book {MR1858793,
TITLE = {Perfect graphs},
SERIES = {Wiley-Interscience Series in Discrete Mathematics and Optimization},
EDITOR = {Ram{\'{\i}}rez Alfons{\'{\i}}n, J. L. and Reed, B.},
PUBLISHER = {John Wiley \& Sons Ltd.},
ADDRESS = {Chichester},
YEAR = {2001},
PAGES = {xxii+362},

}

     
  3. A. Ferreira and H. Reichel, editors. Proceedings of STACS 2001, volume 2010 of Lecture Notes in Computer Science. Springer-Verlag, 2001. 
    @BOOK{FeRe01,
EDITOR = {A. Ferreira and H. Reichel},
KEY = {b-edition},
PUBLISHER = {Springer-Verlag},
SERIES = {Lecture Notes in Computer Science},
TITLE = {{Proceedings of STACS 2001}},
VOLUME = {2010},
YEAR = {2001},

}

     
Thesis
  1. D. Coudert. Algorithmique et optimisation de réseaux de communications optiques. PhD thesis, Université de Nice Sophia-Antipolis (UNSA), Décembre 2001. [POSTSCRIPT ]
    Abstract:
    This thesis deals with optical communication networks, especially free space optical networks and optical fiber networks. First we address the design of free space optical networks using the Optical Transpose Interconnection System (OTIS) architecture defined in [MMHE93]. We give a model of these networks with H(p,q,d) digraphs which we characterize. We take a specific interest in isomorphisms between these digraphs and well known digraphs (de Bruijn, Kautz and other alphabet graphs). We develop a family of alphabet digraphs which includes a large number of digraphs isomorphic to the de Bruijn and use it to obtain an optimal design of the de Bruijn with OTIS, in terms of minimizing the number of lenses. Then, we study a family of networks modeled by directed hypergraphs and called stack-Kautz, for which we provide routing algorithms and control protocols. In a second part we address the problem of WDM network survivability using protection. This problem consists in using precomputed and dedicated resources in order to ensure traffic continuity if a bundle of fibers breaks down. We describe numerous strategies for protecting the instance and the network. We go more deeply into subnetwork protection where protection resources are shared by sets of request describing a specific subnetwork (circuit). We give an optimal solution to this problem when the network is a cycle and the requests realize the All-to-All pattern. 

    @PHDTHESIS{Cou01b,
author = {D. Coudert},
title = {Algorithmique et optimisation de r\'eseaux de communications optiques},
school = {{Universit\'e de Nice Sophia-Antipolis (UNSA)}},
year = {2001},
month = {D\'ecembre},
abstract = {This thesis deals with optical communication networks, especially free space optical networks and optical fiber networks. First we address the design of free space optical networks using the Optical Transpose Interconnection System (OTIS) architecture defined in [MMHE93]. We give a model of these networks with H(p,q,d) digraphs which we characterize. We take a specific interest in isomorphisms between these digraphs and well known digraphs (de Bruijn, Kautz and other alphabet graphs). We develop a family of alphabet digraphs which includes a large number of digraphs isomorphic to the de Bruijn and use it to obtain an optimal design of the de Bruijn with OTIS, in terms of minimizing the number of lenses. Then, we study a family of networks modeled by directed hypergraphs and called stack-Kautz, for which we provide routing algorithms and control protocols. In a second part we address the problem of WDM network survivability using protection. This problem consists in using precomputed and dedicated resources in order to ensure traffic continuity if a bundle of fibers breaks down. We describe numerous strategies for protecting the instance and the network. We go more deeply into subnetwork protection where protection resources are shared by sets of request describing a specific subnetwork (circuit). We give an optimal solution to this problem when the network is a cycle and the requests realize the All-to-All pattern. },
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/these.ps.gz} 
}

     
Articles in journal or book's chapters
  1. H. Everett, C. M. H. de Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, and B. Reed. Even pairs. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 67--92. Wiley, Chichester, 2001. 
    @incollection {MR1861358,
AUTHOR = {Everett, H. and de Figueiredo, C. M. H. and Linhares-Sales, C. and Maffray, F. and Porto, O. and Reed, B.},
TITLE = {Even pairs},
BOOKTITLE = {Perfect graphs},
SERIES = {Wiley-Intersci. Ser. Discrete Math. Optim.},
PAGES = {67--92},
PUBLISHER = {Wiley},
ADDRESS = {Chichester},
YEAR = {2001},

}

     
  2. A. Ferreira. Parallel Computing: Models. In C. A. Floudas and P. Pardalos, editors,Encyclopedia of Optimization -- Vol. IV, pages 264--269. Kluwer Academic Publisher, Boston (USA), 2001. 
    @INCOLLECTION{Fer01,
AUTHOR = {A. Ferreira},
BOOKTITLE = {Encyclopedia of Optimization -- Vol. IV},
EDITOR = {C. A. Floudas and P. Pardalos},
KEY = {bc-chapter},
PAGES = {264--269},
PUBLISHER = {Kluwer Academic Publisher, Boston (USA)},
TITLE = {{Parallel Computing: Models}},
YEAR = {2001},

}

     
  3. R. Hayward and B. Reed. Forbidding holes and antiholes. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 113--137. Wiley, Chichester, 2001. 
    @incollection {MR1861360,
AUTHOR = {Hayward, R. and Reed, B.},
TITLE = {Forbidding holes and antiholes},
BOOKTITLE = {Perfect graphs},
SERIES = {Wiley-Intersci. Ser. Discrete Math. Optim.},
PAGES = {113--137},
PUBLISHER = {Wiley},
ADDRESS = {Chichester},
YEAR = {2001},

}

     
  4. B. Reed. From conjecture to theorem. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 13--24. Wiley, Chichester, 2001. 
    @incollection {MR1861356,
AUTHOR = {Reed, B.},
TITLE = {From conjecture to theorem},
BOOKTITLE = {Perfect graphs},
SERIES = {Wiley-Intersci. Ser. Discrete Math. Optim.},
PAGES = {13--24},
PUBLISHER = {Wiley},
ADDRESS = {Chichester},
YEAR = {2001},

}

     
  5. B. Reed. A gentle introduction to semi-definite programming. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 233--259. Wiley, Chichester, 2001. 
    @incollection {MR1861365,
AUTHOR = {Reed, B.},
TITLE = {A gentle introduction to semi-definite programming},
BOOKTITLE = {Perfect graphs},
SERIES = {Wiley-Intersci. Ser. Discrete Math. Optim.},
PAGES = {233--259},
PUBLISHER = {Wiley},
ADDRESS = {Chichester},
YEAR = {2001},

}

     
  6. J.-P. Allouche and M. Cosnard. Non-integer bases, iteration of continuous real maps, and an arithmetic self-similar set. Acta Mathematica Hungarica, 91:325--332, 2001. 
    @article{AlCo01,
author={J.-P. Allouche and M. Cosnard},
title={Non-integer bases, iteration of continuous real maps, and an arithmetic self-similar set},
journal={Acta Mathematica Hungarica},
volume={91},
year={2001},
pages={325--332},

}

     
  7. E. Altman, E. Baçsar, T. Jiménez, and N. Shimkin. Competitive Routing in Networks with Polynomial Cost. IEEE Trans. on Automatic Control, 2001. 
    @ARTICLE{ABJ+01,
AUTHOR="E. Altman and E. Ba{\c c}sar and T. Jiménez and N. Shimkin",
TITLE="Competitive Routing in Networks with Polynomial Cost",
JOURNAL="IEEE Trans. on Automatic Control",
YEAR="2001" 
}

     
  8. E. Altman, T. Jiménez, and G. Koole. Comparing tandem queueing systems and their fluid limits. PEIS, (2), 2001. 
    @ARTICLE{AJK01,
AUTHOR="E. Altman and T. Jiménez and G. Koole",
TITLE="Comparing tandem queueing systems and their fluid limits",
YEAR="2001",
JOURNAL="PEIS",
NUMBER="2" 
}

     
  9. B. Beauquier, O. Delmas, and S. Pérennes. Tight Bounds for Broadcasting in the Linear Cost Model. Journal of Interconnection Network, 2(2):175--188, 2001. 
    @Article{BDP01,
author = {B. Beauquier and O. Delmas and S. P\'erennes},
title = "Tight Bounds for Broadcasting in the Linear Cost Model",
journal = {Journal of Interconnection Network},
year = {2001},
volume = {2},
number = {2},
pages = {175--188},
publisher = {World Scientific},

}

     
  10. P. Bergé, A. Ferreira, J. Galtier, and J.-N. Petit. A Probabilistic Study of Inter-Satellite Links Load in Polar Orbit Satellite Constellations. International Journal on Telecommunication Systems, 18(1-3):123--135, 2001. [PDF ] 
    @ARTICLE{BFGP01,
AUTHOR = {P. Berg\'e and A. Ferreira and J. Galtier and J.-N. Petit},
JOURNAL = {International Journal on Telecommunication Systems},
NUMBER = {1-3},
PAGES = {123--135},
TITLE = {{A Probabilistic Study of Inter-Satellite Links Load in Polar Orbit Satellite Constellations}},
VOLUME = {18},
YEAR = {2001},
PDF = {ftp://ftp-sop.inria.fr/mascotte/Publications/BFGP01.pdf},

}

     
  11. J-C. Bermond, X. Muñoz, and A. Marchetti-Spaccamela. A Broadcasting Protocol in Line Digraphs. Journal of Parallel and Distributed Computing, 61(8):1013--1032, August 2001. [PDF ] 
    @Article{BMM01,
author = "J-C. Bermond and X. Mu{\~n}oz and A. Marchetti-Spaccamela",
title = "A Broadcasting Protocol in Line Digraphs",
journal = "Journal of Parallel and Distributed Computing",
volume = "61",
number = "8",
pages = "1013--1032",
month = "August",
year = "2001",
PDF = "http://www-sop.inria.fr/members/Jean-Claude.Bermond/PUBLIS/BMM01.pdf",

}

     
  12. M. Cosnard and E. Jeannot. Automatic Parallelization Techniques Based on Compact DAG Extraction and Symbolic Scheduling. Parallel Processing Letters, 11(1):151--168, 2001. 
    @Article{CoJe01,
author = {M. Cosnard and E. Jeannot},
title = "Automatic Parallelization Techniques Based on Compact DAG Extraction and Symbolic Scheduling",
journal = {Parallel Processing Letters},
year = {2001},
volume = {11},
number = {1},
pages = {151--168} 
}

     
  13. M. Diallo, A. Ferreira, and A. Rau-Chaplin. A note on communication-efficient deterministic p aralle algorithms for planar point location and 2D Voronoi diagram. Parallel Processing Letters, 11(2/3):327--340, 2001. 
    @ARTICLE{DFR01,
AUTHOR = {M. Diallo and A. Ferreira and A. Rau-Chaplin},
JOURNAL = {Parallel Processing Letters},
NUMBER = {2/3},
PAGES = {327--340},
TITLE = {{A note on communication-efficient deterministic p aralle algorithms for planar point location and 2D Voronoi diagram}},
VOLUME = {11},
YEAR = {2001},

}

     
  14. A. Ferreira, J. Galtier, J.-N. Petit, and H. Rivano. Re-routing algorithms in a meshed satellite constellation. Annals of Telecommunications, 56(3/4):169--174, march/april 2001. [PDF ]
    Abstract:
    In this paper we present a simple model for satellite constellations with polar orbits and inter-satellite links. This model is used to propose and study two algorithms for routing and re-routing communications, which aim at improving the quality of service for long communications. In order to study these algorithms, we have developed a satellite constellation simulator. Some of its results are presented.

    @ARTICLE{FGPR01,
author = {A. Ferreira and J. Galtier and J.-N. Petit and H. Rivano},
title = {Re-routing algorithms in a meshed satellite constellation},
journal = {Annals of Telecommunications},
year = {2001},
volume = {56},
pages = {169--174},
number = {3/4},
month = {march/april},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/FGPR01.pdf},
abstract = {In this paper we present a simple model for satellite constellations with polar orbits and inter-satellite links. This model is used to propose and study two algorithms for routing and re-routing communications, which aim at improving the quality of service for long communications. In order to study these algorithms, we have developed a satellite constellation simulator. Some of its results are presented.} 
}

     
  15. M. Flammini and S. Pérennes. On the optimality of general lower bounds for broadcasting and gossiping. SIAM J. Discrete Math., 14(2):267--282, 2001. 
    @article{FlPe01,
author= { Flammini, M. and P\'erennes, S. },
title= { On the optimality of general lower bounds for broadcasting and gossiping },
journal= { SIAM J. Discrete Math. },
volume= { 14 },
year= { 2001 },
number= { 2 },
pages= { 267--282 },
issn= { 1095-7146 },

}

     
  16. P. Fraigniaud, A. Pelc, D. Peleg, and S. Pérennes. Assigning labels in unknown network with a leader. Distributed Computing, 14(3):163--183, 2001. 
    @article{FPPP01,
title= { Assigning labels in unknown network with a leader },
author= { P. Fraigniaud and A. Pelc and D. Peleg and S. P\'erennes },
journal= { Distributed Computing },
volume= { 14 },
number= { 3 },
pages= { 163--183 },
year= { 2001 },

}

     
  17. J. Galtier. Geographical reservation for guaranteed handover and routing in low earth orbit constellations. Telecommunication Systems, 18(1/3):101--121, 2001. [PDF ] 
    @Article{Gal01a,
author = {J. Galtier},
title = {Geographical reservation for guaranteed handover and routing in low earth orbit constellations},
journal = {Telecommunication Systems},
year = {2001},
volume = {18},
number = {1/3},
pages = {101--121},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Gal01a.pdf},

}

     
  18. L. Gargano, P. Hell, and S. Pérennes. Coloring all directed paths in a symmetric tree, with an application to optical networks. Journal of Graph Theory, 38(4):183--196, 2001. 
    @article{GHP01,
author= { L. Gargano and P. Hell and S. P\'erennes },
title= { Coloring all directed paths in a symmetric tree, with an application to optical networks },
journal= { Journal of Graph Theory },
year= { 2001 },
volume= { 38 },
number= { 4 },
pages= { 183--196 },

}

     
  19. L. Gargano, A. Pelc, S. Pérennes, and U. Vaccaro. Efficient communication in unknown networks. Networks, 38(1):39--49, 2001. 
    @article{GPPV01,
author= { Gargano, L. and Pelc, A. and P\'erennes, S. and Vaccaro, U. },
title= { Efficient communication in unknown networks },
journal= { Networks },
volume= { 38 },
year= { 2001 },
number= { 1 },
pages= { 39--49 },
issn= { 0028-3045 },

}

     
  20. F. Havet. Channel assignement and multicolouring of the induced subgraphs of the triangular lattice. Discrete Mathematics, 233:219--231, 2001. 
    @ARTICLE{Havet01a,
AUTHOR = "F. Havet",
TITLE = "Channel assignement and multicolouring of the induced subgraphs of the triangular lattice",
JOURNAL = "Discrete Mathematics",
VOLUME = "233",
YEAR = "2001",
PAGES ="219--231",

}

     
  21. M.-C. Heydemann, N. Marlin, and S. Pérennes. Complete Rotations in Cayley Graphs. European Journal of Combinatorics, 22(2):179-196, 2001. [WWW ] 
    @article{HMP00,
author= { M.-C. Heydemann and N. Marlin and S. P\'erennes },
title= { Complete Rotations in Cayley Graphs },
journal= { European Journal of Combinatorics },
year= { 2001 },
volume = {22},
number = {2},
pages = {179-196},
url = {http://dx.doi.org/10.1006/eujc.2000.0460},

}

     
  22. C. Linhares-Sales, F. Maffray, and B. Reed. Recognizing planar strict quasi-parity graphs. Graphs Combin., 17(4):745--757, 2001. 
    @article {MR1876582,
AUTHOR = {Linhares-Sales, C. and Maffray, F. and Reed, B.},
TITLE = {Recognizing planar strict quasi-parity graphs},
JOURNAL = {Graphs Combin.},
VOLUME = {17},
YEAR = {2001},
NUMBER = {4},
PAGES = {745--757},

}

     
  23. D. Rautenbach and B. Reed. The Erdos-Pósa property for odd cycles in highly connected graphs. Combinatorica, 21(2):267--278, 2001.
    Note: Paul Erdos and his mathematics (Budapest, 1999). 
    @article {MR1832451,
AUTHOR = {Rautenbach, D. and Reed, B.},
TITLE = {The {E}rd{\H o}s-{P}\'osa property for odd cycles in highly connected graphs},
NOTE = {Paul Erd\H os and his mathematics (Budapest, 1999)},
JOURNAL = {Combinatorica},
VOLUME = {21},
YEAR = {2001},
NUMBER = {2},
PAGES = {267--278},

}

     
Conference's articles
  1. J-C. Bermond, L. Chacon, D. Coudert, and F. Tillerot. A Note on Cycle Covering. In ACM Symposium on Parallel Algorithms and Architectures -- SPAA, Crete island, Greece, pages 310-311, 4-6 July 2001. [POSTSCRIPT ]
    Abstract:
    This study considers the design of a survivable WDM network based on covering the initial network with sub-networks, which are protected independently from each other.

    @INPROCEEDINGS{BC+01a,
author = {J-C. Bermond and L. Chacon and D. Coudert and F. Tillerot},
title = {{A Note on Cycle Covering}},
booktitle = {ACM Symposium on Parallel Algorithms and Architectures -- SPAA},
year = {2001},
pages = {310-311},
address = {Crete island, Greece},
month = {4-6 July},
abstract = {This study considers the design of a survivable WDM network based on covering the initial network with sub-networks, which are protected independently from each other.},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCCT-SPAA01.ps.gz} 
}

     
  2. J-C. Bermond, L. Chacon, D. Coudert, and F. Tillerot. Cycle Covering. In International Colloquium on Structural Information and Communication Complexity -- SIROCCO, Proceedings in Informatics 11, Vall de Nuria, Spain, pages 21-34, 27-29 June 2001. Carleton Scientific. [PDF ] [POSTSCRIPT ]
    Abstract:
    This paper considers the design of a survivable WDM network based on covering the initial network with sub-networks, which are protected independently from each other. We focus on the case where the optical WDM network is a ring, there are requests between any pair of vertices and the covering is done with small cycles. This problem can be modelled as follows: Find a covering of the edges of a logical graph $I$ (here the complete graph $K_n$) by subgraphs $I_k$ of a certain kind (here cycles $C_k$ of length $k$), such that, for each $I_k$, there exists in the physical graph $G$ (here $C_n$) a disjoint routing of the edges of $I_k$. The aim is to minimize the number of subgraphs $I_k$ in the covering. We give optimal solutions for that problem.

    @INPROCEEDINGS{BC+01b,
author = {J-C. Bermond and L. Chacon and D. Coudert and F. Tillerot},
title = {{Cycle Covering}},
booktitle = {International Colloquium on Structural Information and Communication Complexity -- SIROCCO},
year = {2001},
series = {Proceedings in Informatics 11},
pages = {21-34},
address = {Vall de Nuria, Spain},
month = {27-29 June},
publisher = {Carleton Scientific},
abstract = {This paper considers the design of a survivable WDM network based on covering the initial network with sub-networks, which are protected independently from each other. We focus on the case where the optical WDM network is a ring, there are requests between any pair of vertices and the covering is done with small cycles. This problem can be modelled as follows: Find a covering of the edges of a logical graph $I$ (here the complete graph $K_n$) by subgraphs $I_k$ of a certain kind (here cycles $C_k$ of length $k$), such that, for each $I_k$, there exists in the physical graph $G$ (here $C_n$) a disjoint routing of the edges of $I_k$. The aim is to minimize the number of subgraphs $I_k$ in the covering. We give optimal solutions for that problem.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCCT-SIROCCO01.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/BCCT-SIROCCO01.ps.gz} 
}

     
  3. J-C. Bermond, F. Havet, and D. Tóth. Design of fault tolerant on board networks with priorities. In $3^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2001), Saint-Jean-de-Luz , France, pages 95--98, Mai 2001. 
    @InProceedings{BHT01,
AUTHOR={J-C. Bermond and F. Havet and D. T\'oth},
TITLE={Design of fault tolerant on board networks with priorities},
booktitle = {$3^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2001)},
pages = {95--98},
year = {2001},
address = {Saint-Jean-de-Luz , France},
month = {Mai} 
}

     
  4. S. Bertrand, A. Laugier, and P. Mahey. Routing flows in networks with heterogenous protocols and path-dependent edge costs. In $3^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2001), Saint-Jean-de-Luz , France, pages 55--60, Mai 2001. 
    @InProceedings{BLM01,
AUTHOR={S. Bertrand and A. Laugier and P. Mahey},
TITLE={Routing flows in networks with heterogenous protocols and path-dependent edge costs},
booktitle = {$3^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2001)},
pages = {55--60},
year = {2001},
address = {Saint-Jean-de-Luz , France},
month = {Mai} 
}

     
  5. A. Caminada, A. Ferreira, and L. Floriani. Principal Component Analysis for data volume reduction in experimental analysis of heuristics. In Proceedings of GECCO 2001 Workshop on Real-life Evolutionary Design Optimisation, San Francisco (USA), 2001. 
    @INPROCEEDINGS{CFF01,
AUTHOR = {A. Caminada and A. Ferreira and L. Floriani},
ADDRESS = {San Francisco (USA)},
BOOKTITLE = {Proceedings of GECCO 2001 Workshop on Real-life Evolutionary Design Optimisation},
TITLE = {{Principal Component Analysis for data volume reduction in experimental analysis of heuristics}},
YEAR = {2001},

}

     
  6. I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, P. Persiano, and H. Rivano. Approximate Constrained Bipartite Edge Coloring. In V.B. Le A. Branstädt, editor, 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01), volume 2204 of Lecture Notes in Computer Science, Boltenhagen, Germany, pages 21--31, June 2001. Springer-Verlag. [PDF ]
    Abstract:
    We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard event for bipartite graphs of maximum degree three [5].

    @INPROCEEDINGS{CFK+01b,
author = {I. Caragiannis and A. Ferreira and C. Kaklamanis and S. Pérennes and P. Persiano and H. Rivano},
title = {Approximate Constrained Bipartite Edge Coloring},
booktitle = {27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01)},
year = {2001},
editor = {A. Branst\"adt, V.B. Le},
volume = {2204},
series = {Lecture Notes in Computer Science},
pages = {21--31},
address = {Boltenhagen, Germany},
month = {June},
publisher = {Springer-Verlag},
abstract = {We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard event for bipartite graphs of maximum degree three [5].},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/cfk01b.pdf} 
}

     
  7. I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, and H. Rivano. Fractional path coloring on bounded degree trees. In F. Orejas, P. G. Spirakis, and J. van Leeuwen, editors, Proceedings of the 28th ICALP, volume 2076 of Lecture Notes in Computer Science, Crete, Greece, pages 732--743, July 2001. Springer-Verlag. [PDF ]
    Abstract:
    This paper addresses the natural relaxation of the path coloring problem, in which one needs to color directed paths on a symmetric directed graph with a minimum number of colors, in such a way that paths using the same arc of the graph have different colors. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) all-optical networks.

    @INPROCEEDINGS{CFKPR01,
author = {I. Caragiannis and A. Ferreira and C. Kaklamanis and S. Pérennes and H. Rivano},
title = {Fractional path coloring on bounded degree trees},
booktitle = {Proceedings of the 28th ICALP},
year = {2001},
editor = {F. Orejas and P. G. Spirakis and van Leeuwen, J.},
volume = {2076},
series = {Lecture Notes in Computer Science},
pages = {732--743},
address = {Crete, Greece},
month = {July},
publisher = {Springer-Verlag},
abstract = {This paper addresses the natural relaxation of the path coloring problem, in which one needs to color directed paths on a symmetric directed graph with a minimum number of colors, in such a way that paths using the same arc of the graph have different colors. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) all-optical networks.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/cfk01.pdf} 
}

     
  8. S. Choplin. Virtual Path Layout in ATM Path with given hop count. In International Conference on Networking, ICN01, volume 2094, Part II of LNCS, pages 527--537, 2001. Springer. 
    @InProceedings{Cho01,
author = {S. Choplin},
title = {Virtual Path Layout in {ATM} Path with given hop count},
booktitle = {International Conference on Networking, ICN01},
pages = {527--537},
year = {2001},
volume = {2094, Part II},
series = {LNCS},
publisher = {Springer} 
}

     
  9. H. Cirstea, C. Kirchner, and L. Liquori. Matching Power. In RTA, International Conference on Rewriting Techniques and Applications, volume 2051 of Lecture Notes in Computer Science, pages 77--92, 2001. [POSTSCRIPT ] 
    @inproceedings{CKL01a,
author = {H. Cirstea and C. Kirchner and L. Liquori},
title = {{Matching Power}},
booktitle = {RTA, International Conference on Rewriting Techniques and Applications},
pages = {77--92},
series = lncs,
VOLUME = {2051},
year = {2001},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/rta-01.ps.gz} 
}

     
  10. H. Cirstea, C. Kirchner, and L. Liquori. The Rho Cube. In FoSSaCS, International Conference on Foundations of Software Science and Computation Structures, volume 2030 of Lecture Notes in Computer Science, pages 168--183, 2001. [POSTSCRIPT ] 
    @inproceedings{CKL01b,
author = {H. Cirstea and C. Kirchner and L. Liquori},
title = {{The Rho Cube}},
booktitle = {FoSSaCS, International Conference on Foundations of Software Science and Computation Structures},
volume = {2030},
series = lncs,
year = {2001},
pages = {168--183},
POSTSCRIPT= {http://www-sop.inria.fr/mascotte/Luigi.Liquori/PAPERS/fossacs-01.ps.gz} 
}

     
  11. M. Cosnard and L. Grigori. A Parallel Algorithm for Sparse Symbolic LU Factorization without Pivoting on Out of Core Matrices. In 15th ACM International Conference on Supercomputing (ICS'01), 2001. 
    @InProceedings{CoGr01,
author = {M. Cosnard and L. Grigori},
title = {A Parallel Algorithm for Sparse Symbolic LU Factorization without Pivoting on Out of Core Matrices},
booktitle = {15th ACM International Conference on Supercomputing (ICS'01)},
year = {2001},
month = {},
pages = {} 
}

     
  12. D. Coudert and X. Muñoz. How Graph Theory can help Communications Engineering. In D.K.Gautam, editor, Broad band optical fiber communications technology -- BBOFCT, Jalgaon, India, pages 47-61, December 2001. Nirtali Prakashan.
    Note: Invited paper. [POSTSCRIPT ]
    Abstract:
    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 this field. We deal in this paper with network topologies, resource competition, state transition diagrams and specific models for optical networks.

    @INPROCEEDINGS{CM01,
author = {D. Coudert and X. Muñoz},
title = {{How Graph Theory can help Communications Engineering}},
booktitle = {Broad band optical fiber communications technology -- BBOFCT},
year = {2001},
editor = {D.K.Gautam},
pages = {47-61},
address = {Jalgaon, India},
month = {December},
publisher = {Nirtali Prakashan},
note = {Invited paper},
abstract = { 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 this field. We deal in this paper with network topologies, resource competition, state transition diagrams and specific models for optical networks.},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/CM-BBOFCT01.ps.gz} 
}

     
  13. D. Coudert. Chemins disjoints de poids minimum pour la sécurisation de réseaux de télécommunications. In Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications -- AlgoTel, St-Jean de Luz, France, pages 47-53, 28-30 Mai 2001. [POSTSCRIPT ]
    Abstract:
    Cette \'etude s'int\'eresse \`a la planification de r\'eseaux WDM tol\'erants aux pannes. Nous cherchons \`a \'etablir, pour chaque couple de n{\oe}uds du r\'eseau, deux chemins de communication disjoints, l'un \'etant r\'eserv\'e \`a la protection de l'autre. Pour un r\'eseau \`a $n$ n{\oe}uds et $m$ liens de communications, nous donnons un algorithme en $O(n(m+n\log n))$, permettant de calculer depuis un n{\oe}ud donn\'e et vers chacun des autres n{\oe}uds deux chemins arc-disjoints dont la somme des poids est minimale. Ceci am\'eliore la complexit\'e des solutions bas\'ees sur les algorithmes de flot de poids minimum, qui est en temps $O(m(m+n\log n)\log n)$ pour un seul couple de sommets.

    @INPROCEEDINGS{Cou01,
author = {D. Coudert},
title = {Chemins disjoints de poids minimum pour la sécurisation de réseaux de télécommunications},
booktitle = {{Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications -- AlgoTel}},
year = {2001},
pages = {47-53},
address = {St-Jean de Luz, France},
month = {28-30 Mai},
abstract = { Cette \'etude s'int\'eresse \`a la planification de r\'eseaux WDM tol\'erants aux pannes. Nous cherchons \`a \'etablir, pour chaque couple de n{\oe}uds du r\'eseau, deux chemins de communication disjoints, l'un \'etant r\'eserv\'e \`a la protection de l'autre. Pour un r\'eseau \`a $n$ n{\oe}uds et $m$ liens de communications, nous donnons un algorithme en $O(n(m+n\log n))$, permettant de calculer depuis un n{\oe}ud donn\'e et vers chacun des autres n{\oe}uds deux chemins arc-disjoints dont la somme des poids est minimale. Ceci am\'eliore la complexit\'e des solutions bas\'ees sur les algorithmes de flot de poids minimum, qui est en temps $O(m(m+n\log n)\log n)$ pour un seul couple de sommets.},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/Cou-AlgoTel01.ps.gz} 
}

     
  14. S. Céroi and F. Havet. Trees with three leaves are (n + 1)-unavoidable. In Jayme Szwarcfiter and Siang Song, editors, Electronic Notes in Discrete Mathematics, volume 7, 2001. Elsevier Science Publishers. 
    @inproceedings{CeHa01,
author = "S. Céroi and F. Havet",
title = "Trees with three leaves are (n + 1)-unavoidable",
booktitle = "Electronic Notes in Discrete Mathematics",
volume = "7",
publisher = "Elsevier Science Publishers",
editor = "Jayme Szwarcfiter and Siang Song",
year = "2001" 
}

     
  15. O. Dalle, J. Radzik, C. Rigal, F. Rodière, and C. Saroléa. ASIMUT: An Environment for the Simulation of Multi-Media Satellite Telecommunication Networks. In 19th International Communications Satellite Systems Conference (ICSSC), Toulouse, France, April 2001. AIAA. 
    @inproceedings{DRR+01,
AUTHOR = {Dalle, O. and Radzik, J. and Rigal, C. and Rodi\`ere, F. and Sarol\'ea, C.},
TITLE = {{ASIMUT}: An Environment for the Simulation of Multi-Media Satellite Telecommunication Networks},
BOOKTITLE = {19th International Communications Satellite Systems Conference (ICSSC)},
YEAR = 2001,
ORGANIZATION = {AIAA},
MONTH = apr,
ADDRESS = {Toulouse, France} 
}

     
  16. H. Everett, C. M. H. de Figueiredo, S. Klein, and B. Reed. Bull-reducible Berge graphs are perfect. In Comb01---Euroconference on Combinatorics, Graph Theory and Applications, volume 10 of Electron. Notes Discrete Math., Amsterdam, pages 3 pp. (electronic), 2001. Elsevier. 
    @inproceedings{MR2154484,
AUTHOR = {Everett, H. and de Figueiredo, C. M. H. and Klein, S. and Reed, B.},
TITLE = {Bull-reducible {B}erge graphs are perfect},
BOOKTITLE = {Comb01---Euroconference on Combinatorics, Graph Theory and Applications},
SERIES = {Electron. Notes Discrete Math.},
VOLUME = {10},
PAGES = {3 pp. (electronic)},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2001},

}

     
  17. G. Fertin, A. Raspaud, and B. Reed. On star coloring of graphs. In Graph-theoretic concepts in computer science (Boltenhagen, 2001), volume 2204 of Lecture Notes in Comput. Sci., Berlin, pages 140--153, 2001. Springer. 
    @inproceedings{MR1905628,
AUTHOR = {Fertin, G. and Raspaud, A. and Reed, B.},
TITLE = {On star coloring of graphs},
BOOKTITLE = {Graph-theoretic concepts in computer science (Boltenhagen, 2001)},
SERIES = {Lecture Notes in Comput. Sci.},
VOLUME = {2204},
PAGES = {140--153},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
YEAR = {2001},

}

     
  18. J. Galtier. Semi-Definite Programming as a Simple Extension to Linear Programming: Convex Optimization with Queueing, Equity and Other Telecom Functionals. In $3^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2001), Saint-Jean-de-Luz, pages 21--28, May 2001. 
    @InProceedings{Gal01b,
author = {J. Galtier},
title = {Semi-Definite Programming as a Simple Extension to Linear Programming: Convex Optimization with Queueing, Equity and Other Telecom Functionals},
booktitle = {$3^{e}$ rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2001)},
pages = {21--28},
year = 2001,
address = {Saint-Jean-de-Luz},
month = {May} 
}

     
  19. J. Galtier and A. Oliveira. A proposal to study satellite constellation routing via classical linear programming methods. In 43rd conference of the Canadian Operations Research Society, 2001. 
    @InProceedings{GaOl01,
author = {J. Galtier and A. Oliveira},
title = {A proposal to study satellite constellation routing via classical linear programming methods},
booktitle = {43rd conference of the Canadian Operations Research Society},
year = 2001 
}

     
  20. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance Labeling in Graphs. In SODA'01, pages 210--219, 2001. 
    @InProceedings{GPPR01,
title={Distance Labeling in Graphs},
author={C. Gavoille and D. Peleg and S. P\'erennes and R. Raz},
booktitle ={ SODA'01},
pages={210--219},
year={2001},

}

     
  21. C. Gomes and A. H. Dominguez. Modelagem e Implementação do módulo tutor do ambiente AVA-TA@ead. In Anais XI Encontro de Iniciação Cientìfica da Universidade Federal de Alagoas, 2001. 
    @INPROCEEDINGS{GD01,
AUTHOR = {C. Gomes and A. H. Dominguez},
TITLE = {Modelagem e Implementa\c c\~ao do m\'odulo tutor do ambiente AVA-TA@ead},
BOOKTITLE = {Anais XI Encontro de Inicia\c c\~ao Cient\'ifica da Universidade Federal de Alagoas},
SCHOOL = {Alagoas Federal University, AL},
YEAR = {2001},

}

     
  22. F. Havet and M. Wennink. The Push Tree Problem. In SPAA'01: 13th ACM Symposium on Parallel Algorithms and Architectures, Crète , Grèce, pages 318--319, Juillet 2001. 
    @INPROCEEDINGS{HaWe01,
AUTHOR = "F. Havet and M. Wennink",
TITLE = "The Push Tree Problem",
BOOKTITLE = " SPAA'01: 13th ACM Symposium on Parallel Algorithms and Architectures",
YEAR = "2001",
address = {Cr\`ete , Gr\`ece},
month = {Juillet},
PAGES = "318--319",

}

     
  23. C. McDiarmid and B. Reed. Channel assignment on nearly bipartite and bounded treewidth graphs. In Comb01---Euroconference on Combinatorics, Graph Theory and Applications, volume 10 of Electron. Notes Discrete Math., Amsterdam, pages 4 pp. (electronic), 2001. Elsevier. 
    @inproceedings{MR2154509,
AUTHOR = {McDiarmid, C. and Reed, B.},
TITLE = {Channel assignment on nearly bipartite and bounded treewidth graphs},
BOOKTITLE = {Comb01---Euroconference on Combinatorics, Graph Theory and Applications},
SERIES = {Electron. Notes Discrete Math.},
VOLUME = {10},
PAGES = {4 pp. (electronic)},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2001},

}

     
  24. M. Molloy and B. Reed. Colouring graphs when the number of colours is nearly the maximum degree. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, New York, pages 462--470 (electronic), 2001. ACM. 
    @inproceedings {MR2120347,
AUTHOR = {Molloy, M. and Reed, B.},
TITLE = {Colouring graphs when the number of colours is nearly the maximum degree},
BOOKTITLE = {Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing},
PAGES = {462--470 (electronic)},
PUBLISHER = {ACM},
ADDRESS = {New York},
YEAR = {2001},

}

     
  25. D. Rautenbach and B. Reed. Approximately covering by cycles in planar graphs. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), Philadelphia, PA, pages 402--406, 2001. SIAM. 
    @inproceedings {MR1958432,
AUTHOR = {Rautenbach, D. and Reed, B.},
TITLE = {Approximately covering by cycles in planar graphs},
BOOKTITLE = {Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001)},
PAGES = {402--406},
PUBLISHER = {SIAM},
ADDRESS = {Philadelphia, PA},
YEAR = {2001},

}

     
  26. H. Rivano. Planification de réseaux optiques WDM k-fibres. In AlgoTel'01 - $3^{e}$ Rencontres Françaises sur les Aspects Algorithmiques des Télécommunications, Saint-Jean-de-Luz, France, pages 41--46, mai 2001. [WWW ] [PDF ]
    Abstract:
    Cet article propose une modélisation en termes d'hypergraphe du problème d'affectation de longueurs d'onde à des chemins dans un réseau \wdm $k$-fibres. La contrainte classique rencontrée dans les réseaux \wdm change de nature lorsque plusieurs fibres connectent physiquement deux noeuds du réseau. Nous montrons l'équivalence entre ce problème et la coloration $k${\em -tolérante} de {\em l'hypergraphe des conflits} des chemins. Nous exploitons ensuite deux résultats d'algorithmique aléatoire de la littérature pour donner une première approximation du dimensionnement des réseaux $k$-fibres.

    @INPROCEEDINGS{Riv01,
author = {H. Rivano},
title = {Planification de réseaux optiques WDM k-fibres},
booktitle = {AlgoTel'01 - $3^{e}$ Rencontres Françaises sur les Aspects Algorithmiques des Télécommunications},
year = {2001},
pages = {41--46},
address = {Saint-Jean-de-Luz, France},
month = {mai},
abstract = {Cet article propose une modélisation en termes d'hypergraphe du problème d'affectation de longueurs d'onde à des chemins dans un réseau \wdm $k$-fibres. La contrainte classique rencontrée dans les réseaux \wdm change de nature lorsque plusieurs fibres connectent physiquement deux noeuds du réseau. Nous montrons l'équivalence entre ce problème et la coloration $k${\em -tolérante} de {\em l'hypergraphe des conflits} des chemins. Nous exploitons ensuite deux résultats d'algorithmique aléatoire de la littérature pour donner une première approximation du dimensionnement des réseaux $k$-fibres.},
pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/riv01.pdf},
url = {http://ares.insa-lyon.fr/tarot/jsp/site/Portal.jsp?page_id=14} 
}

     
Internal reports
  1. E. Altman, J. Galtier, and C. Touati. On fairness in bandwidth allocation. Rapport de Recherche 4269, INRIA, Sophia Antipolis, septembre 2001. 
    @techreport{AGT,
title="On fairness in bandwidth allocation",
author="E. Altman and J. Galtier and C. Touati",
month="septembre",
year="2001",
number="4269",
type="Rapport de Recherche",
institution="INRIA, Sophia Antipolis" 
}

     
  2. O. Audouin, C. Blaizot, E. Dotaro, M. Vigoureux, B. Beauquier, J-C. Bermond, B. Bongiovanni, S. Pérennes, M. Syska, S. Bibas, L. Chacon, B. Decocq, E. Didelet, A. Laugier, A. Lisser, A. Ouorou, and F. Tillerot. Planification et Optimisation des Réseaux de Transport Optiques. Rapport final RNRT PORTO, Alcatel Research & Innovation, Projet MASCOTTE (CNRS/INRIA/UNSA) et France Télécom R&D, Sophia Antipolis, December 2001. 
    @TECHREPORT{porto,
AUTHOR = {O. Audouin and C. Blaizot and E. Dotaro and M. Vigoureux and B. Beauquier and J-C. Bermond and B. Bongiovanni and S. Pérennes and M. Syska and S. Bibas and L. Chacon and B. Decocq and E. Didelet and A. Laugier and A. Lisser and A. Ouorou and F. Tillerot},
ADDRESS = {Sophia Antipolis},
INSTITUTION = {Alcatel Research \& Innovation, Projet MASCOTTE (CNRS/INRIA/UNSA) et France Télécom R\&D},
MONTH = dec,
TITLE = {Planification et Optimisation des Réseaux de Transport Optiques},
TYPE = {{R}apport final {RNRT PORTO}},
YEAR = {2001},

}

     
  3. J-C. Bermond, D. Coudert, and M-L. Yu. On DRC-Covering of $K_n$ by cycles. Technical report, INRIA Research Report RR-4299, I3S Research Report I3S/RR-2002-30-FR, 2001. [PDF ] [POSTSCRIPT ] 
    @TECHREPORT{BCY01,
author = {J-C. Bermond and D. Coudert and M-L. Yu},
title = {{On DRC-Covering of $K_n$ by cycles}},
institution = {INRIA Research Report RR-4299, I3S Research Report I3S/RR-2002-30-FR},
year = {2001},
optnote = {RR-4299},
pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/I3SRR-2002-30-FR.pdf},
postscript = {ftp://ftp-sop.inria.fr/mascotte/personnel/David.Coudert/Publication/RR-4299.ps.gz} 
}

     
  4. A. Ferreira, S. Pérennes, A. Richa, H. Rivano, and N. Stier. On the design of multifiber WDM networks. Research Report, INRIA Research Report 4244, August 2001. [WWW ]
    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. We then 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 \npc, and present further results with respect to the complexity of that problem. Finally, we analyze the practical performances of two methodologies based on hypergraph coloring, on existing backbone networks in Europe and in the USA. The first relies on an integer programming formulation and the second consists of a heuristic based on a randomized algorithm. 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$

    @TECHREPORT{FPR+01,
author = {A. Ferreira and S. Pérennes and A. Richa and H. Rivano and N. Stier},
title = {On the design of multifiber WDM networks},
institution = {INRIA Research Report 4244},
year = {2001},
type = {Research Report},
month = {August},
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. We then 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 \npc, and present further results with respect to the complexity of that problem. Finally, we analyze the practical performances of two methodologies based on hypergraph coloring, on existing backbone networks in Europe and in the USA. The first relies on an integer programming formulation and the second consists of a heuristic based on a randomized algorithm. 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$},
url = {http://hal.inria.fr/inria-00072343} 
}

     
  5. A. Ferreira, S. Pérennes, and H. Rivano. Fractional coloring of bounded degree trees. Research Report, INRIA Research Report 4094, January 2001. [WWW ]
    Abstract:
    We study the dipath-coloring problem in bounded degree and treewidth symmetric digraphs, in which one needs to color the dipaths with a minimum number of colors, in such a way that dipaths using the same arc have different colors. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) all optical networks. In this paper, we prove that finding an optimal fractional coloring of such dipaths is polynomial. Our solution is constructive, i.e. we give an effective polynomial algorithm for the problem above. We also show some relationships between the integral and fractional problems, prove some polynomial instances of the coloring problem, and derive a $1 + 5/3e$ approximation for the \wdm problem in symmetric directed trees, where $e$ is the classical Neper constant, improving on previous results. Finally we present computational results suggesting that fractional coloring is a good oracle for a branch and bound strategy for coloring dipaths in symmetric directed trees and cycles.

    @TECHREPORT{FPR01,
author = {A. Ferreira and S. Pérennes and H. Rivano},
title = {Fractional coloring of bounded degree trees},
institution = {INRIA Research Report 4094},
year = {2001},
type = {Research Report},
month = {January},
abstract = {We study the dipath-coloring problem in bounded degree and treewidth symmetric digraphs, in which one needs to color the dipaths with a minimum number of colors, in such a way that dipaths using the same arc have different colors. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) all optical networks. In this paper, we prove that finding an optimal fractional coloring of such dipaths is polynomial. Our solution is constructive, i.e. we give an effective polynomial algorithm for the problem above. We also show some relationships between the integral and fractional problems, prove some polynomial instances of the coloring problem, and derive a $1 + 5/3e$ approximation for the \wdm problem in symmetric directed trees, where $e$ is the classical Neper constant, improving on previous results. Finally we present computational results suggesting that fractional coloring is a good oracle for a branch and bound strategy for coloring dipaths in symmetric directed trees and cycles.},
url = {http://hal.inria.fr/inria-00072538} 
}

     
Miscellaneous
  1. N. Baskiotis. Dimensionnement heuristique des réseaux optiques WDM multifibres. Rapport de stage, ENS Lyon, 2001. 
    @MastersThesis{Bas01,
author = {N. Baskiotis},
title = {Dimensionnement heuristique des r\'eseaux optiques WDM multifibres},
type={Rapport de Licence d'Informatique},
school = {ENS Lyon},
year = {2001},
type = {Rapport de stage},

}

     
  2. O. Bernardi. Réseaux de permutation et tolérance aux pannes. Rapport de Licence d'Informatique, ENS Paris, 2001. 
    @MastersThesis{Ber01,
author = {O. Bernardi},
title = {R\'eseaux de permutation et tol\'erance aux pannes},
school = {ENS Paris},
year = {2001},
type = {Rapport de Licence d'Informatique},

}

     
  3. S. Bhadra. Technique de décodage. Rapport de stage, IIT Madras, 2001. 
    @MastersThesis{Bha01,
author = {S. Bhadra},
title = {Technique de d\'ecodage},
school = {IIT Madras},
year = {2001},
type = {Rapport de stage},

}

     
  4. B. Boschat, A. Cusumano, S. Fourré, and P. Nassif-Bouery. Optimisation de réseaux. Rapport de projet, Maîtrise d'Informatique, Université de Nice Sophia Antipolis, 2001. 
    @MastersThesis{BCFN01,
author = { B. Boschat and A. Cusumano and S. Fourré and P. Nassif-Bouery},
title = {Optimisation de r\'eseaux},
school = {Université de Nice Sophia Antipolis},
year = {2001},
type = {Rapport de projet, Ma\^{i}trise d'Informatique},

}

     
  5. T. Crulli. Partition de domaine en boucles. Rapport de stage, Brown university, 2001. 
    @MastersThesis{Cru01,
author = {T. Crulli},
title = {Partition de domaine en boucles},
school = {Brown university},
year = {2001},
type = {Rapport de stage},

}

     
  6. T. Dilys. Allocation de fréquences. Rapport de stage, IIT Bombay, 2001. 
    @MastersThesis{Dil01,
author = {T. Dilys},
title = {Allocation de fr\'equences},
school = {IIT Bombay},
year = {2001},
type = {Rapport de stage},

}

     
  7. F. Giroire. Minimisation des commutateurs de réseaux de satellites avec excès d'entrées et de sorties. Rapport de Maîtrise d'Informatique, ENS Paris, 2001. 
    @MastersThesis{Gir01,
author = {F. Giroire},
title = {Minimisation des commutateurs de r\'eseaux de satellites avec exc\`es d'entr\'ees et de sorties},
school = {ENS Paris},
year = {2001},
type = {Rapport de Ma\^{i}trise d'Informatique},

}

     
  8. A. Jarry. Protection dans les réseaux optiques: graphes 2-connexes de diamètre fixé. Rapport de DEA, ENS Lyon, 2001. 
    @MastersThesis{Jar01,
author = {A. Jarry},
title = {Protection dans les r\'eseaux optiques: graphes 2-connexes de diam\`etre fix\'e},
school = {ENS Lyon},
year = {2001},
type = {Rapport de DEA},

}

     
  9. J.-F. Lalande. Protection dans les réseaux de télécommunications. Rapport de DEA, ISIMA Clermont-Ferrand, 2001. [PDF ] [POSTSCRIPT ] 
    @MastersThesis{Lal01,
author = {J.-F. Lalande},
title = {Protection dans les réseaux de télécommunications},
school = {ISIMA Clermont-Ferrand},
year = {2001},
type = {Rapport de DEA},
PDF={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Francois.Lalande/articles/rapport_stage_2001_dea.pdf},
POSTSCRIPT={ftp://ftp-sop.inria.fr/mascotte/personnel/Jean-Francois.Lalande/articles/rapport_stage_2001_dea.ps.gz} 
}

     
  10. C. Lekbir and C. Scherhag. Finance algorithmique. Rapport de projet, IMAFA, 2001. 
    @MastersThesis{LeSc01,
author = {C. Lekbir and C. Scherhag},
title = {Finance algorithmique},
school = {IMAFA},
year = {2001},
type = {Rapport de projet},

}

     
  11. S. Rai. Design and optimisation of WDM networks. Rapport de stage, IIT New Delhi, 2001. 
    @MastersThesis{Rai01,
author = {S. Rai},
title = { Design and optimisation of WDM networks},
school = {IIT New Delhi},
year = {2001},
type = {Rapport de stage},

}

     
  12. A. Raux. Site WWW du projet MASCOTTE. Rapport de 2e année, I.U.T., 2001. 
    @MastersThesis{Rau01,
author = {A. Raux},
title = {Site WWW du projet MASCOTTE},
school = {I.U.T.},
year = {2001},
type = {Rapport de 2e ann\'ee},

}

     
  13. S. Romanet. Interface et visualisation 3D pour la simulation de trafic routier. Rapport de Maîtrise, ISTG Grenoble, 2001. 
    @MastersThesis{Rom01,
author = {S. Romanet},
title = {Interface et visualisation 3D pour la simulation de trafic routier},
school = {ISTG Grenoble},
year = {2001},
type = {Rapport de Ma\^{i}trise},

}

     
  14. R. Saint-Gratien. Evaluation et optimisation des performances du système de fichiers MPCFS. Rapport de projet, ESSI, 2001. 
    @MastersThesis{StG01,
author = {R. Saint-Gratien},
title = {Evaluation et optimisation des performances du syst\`eme de fichiers MPCFS},
school = {ESSI},
year = {2001},
type = {Rapport de projet},

}

     
  15. J. Savaresse. Microsimulation de trafic routier. Rapport de 2e année, ISIMA Clermont-Ferrand, 2001. 
    @MastersThesis{Sav01,
author = {J. Savaresse},
title = {Microsimulation de trafic routier},
school = {ISIMA Clermont-Ferrand},
year = {2001},
type = {Rapport de 2e ann\'ee},

}

     
  16. R. Sood. Application du couplage au problème de tournée de véhicules. Rapport de stage, IIT New Delhi, 2001. 
    @MastersThesis{Soo01,
author = {R. Sood},
title = {Application du couplage au probl\`eme de tourn\'ee de v\'ehicules},
school = {IIT New Delhi},
year = {2001},
type = {Rapport de stage},

}

     
  17. N. Stier. Optimisation de réseaux optiques. Rapport de stage, MIT Boston, 2001. 
    @MastersThesis{Sti01,
author = {N. Stier},
title = {Optimisation de r\'eseaux optiques},
school = {MIT Boston},
year = {2001},
type = {Rapport de stage},

}

     
  18. G. Temporal. Conception de réseaux embarqués tolérants aux pannes. Rapport de DEA, Université de Nice Sophia Antipolis, 2001. 
    @MastersThesis{Tem01,
author = {G. Temporal},
title = {Conception de r\'eseaux embarqu\'es tol\'erants aux pannes},
school = {Université de Nice Sophia Antipolis},
year = {2001},
type = {Rapport de DEA},

}

     
  19. C. Vallebella. Routage et groupage dans les réseaux de transport optiques. Rapport de 3e année, ESSI, 2001. 
    @MastersThesis{Val01,
author = {C. Vallebella},
title = {Routage et groupage dans les réseaux de transport optiques},
school = {ESSI},
year = {2001},
type = {Rapport de 3e ann\'ee},

}

     

BACK TO COATI PUBLICATION INDEX


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