[Information sur ces pages]

Graphs & Applications
List of Publications of the Team

(bibtex format)
[home page of the team]

Individual publications
Olivier Baudon
Nicolas Bonichon
Olivier Delmas
Cyril Gavoille
Nicolas Hanusse
Ralf Klasing
Mickaël Montassier
Arnaud Pêcher
André Raspaud
Éric Sopena
Denise Amar (-2006)
Pascal Auillans (-2005)
Dominique Barth (-1994)
Fabrice Bazzaro (-2006)
Abdhala Bel Hala (-1995)
Yon Dourisboure (-2005)
Frédéric Ferchaud (-2006)
Guillaume Fertin (-2000)
Ginette Gauyacq (-2004)
Cyrille Micheneau (-1996)
Pascal Ochem (-2007)
Christophe Paul (-2001)
Alexandre Pinlou (-2007)
Mohammad Hosseini (-2005)
Olivier Togni (-1999)

Copyrights for some of the papers below have been transfered, or will be transfered to various publishers of journals, conferences proceedings, etc. For such papers I am required to post the following notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. Publisher's copyright policy are available at © SIAM, © ACM, © IEEE, © Springer, © Elsevier, © Ideal, © King's College.


[ 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | 1998 | 1997 | 1996 | 1995 | 1994 | 1993 | 1992 | 1991 | 1990 | 1987]


2008

  1. D. Gonçalves and M. Montassier. Acyclic choosability of graphs with small maximum degree. In WG 2005, 31st International Workshop on Graph Theoretic Concepts in Computer Science, Metz, France, June 23-25 2005. D. Kratsch (Ed.): WG2005, LNCS 3787, pp.239-248, Springer-Verlag. Date?

  2. L. Esperet, M. Montassier, and A. Raspaud. Linear choosability of graphs. In EuroComb'05, European conference on Combinatorics, Graph Theory and Applications, Berlin, Germany, September 5-9 2005. Date?



2007

  1. Cyril Gavoille and Arnaud Labourel. Distributed relationship schemes for trees. In 18th Annual International Symposium on Algorithms and Computation (ISAAC), volume 4835 of Lecture Notes in Computer Science, pages 728-738. Springer, December 2007. See [GL07a] for a brief announcement. Slides available here.

  2. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz Kuszner, and Alfredo Navarra. On the complexity of distributed graph coloring with local minimality constraints. Research Report RR-1440-07, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, December 2007. See [GKKN07] for a brief announcement.

  3. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz Kuszner, and Alfredo Navarra. On the complexity of distributed graph coloring with local minimality constraints. Research Report 6399, INRIA, December 2007. See [GKKN07] for a brief announcement.

  4. Cyril Gavoille and Arnaud Labourel. Schéma relationnel distribué pour les arbres. In 9èmes Journées Graphes et Algorithmes, page 19, November 2007. Slides available here.

  5. Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In Lars Arge and Emo Welzl, editors, 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 582-593. Springer, October 2007. Slides available here.

  6. Cyril Gavoille, Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Brief announcement: On the complexity of distributed greedy coloring. In 21st International Symposium on Distributed Computing (DISC), volume 4731 of Lecture Notes in Computer Science, pages 482-484. Springer, September 2007. Slides available here. See [GKKKN07] for an updated version and [GKKKN07b].

  7. Yon Dourisboure, Feodor F. Dragan, Cyril Gavoille, and Chenyu Yan. Spanners for bounded tree-length graphs. Theoretical Computer Science, 383(1):34-44, September 2007. A preliminary version appears as RR-1316-04 (2004) and in SIROCCO '04.

  8. Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In 21st International Symposium on Distributed Computing (DISC), volume 4731 of Lecture Notes in Computer Science, pages 179-192. Springer, September 2007. Slides available here.

  9. Cyril Gavoille and Arnaud Labourel. Brief annoucement: On local representation of distances in trees. In 26th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 246-247. ACM Press, August 2007. See [GL07b] for the full version. Slides available here.

  10. Cyril Gavoille. Localized data structures (keynote talk). In 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), August 2007. Co-located with PODC 2007, See web pages here.

  11. Bruno Courcelle, Cyril Gavoille, Mustapha Kanté, and David Andrew Twigg. Forbidden-set labeling on graphs. In 2nd Workshop on Locality Preserving Distributed Computing Methods (LOCALITY), August 2007. Co-located with PODC 2007, Slides available here.

  12. Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: Information sensitivity of graph coloring. In 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 4596 of Lecture Notes in Computer Science, pages 231-242. Springer, July 2007.

  13. Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, and Zvi Lotker. Universal augmentation schemes for network navigability: Overcoming the \sqrtn-barrier. In 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1-7. ACM Press, June 2007. BEST PAPER AWARD. Slides available here.

  14. Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-diameter decompositions of minor free graphs. In 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 16-24. ACM Press, June 2007. See [AGMW06] for the TR version. See here for a long version.

  15. Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, and Zvi Lotker. A propos des schémas d'augmentation universels pour la navigation dans les réseaux. In 9èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 23-26, May 2007.

  16. Youssou Dieng and Cyril Gavoille. Routage dans les graphes cellulaires. In 9èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 91-94, May 2007.

  17. Cyril Gavoille. An overview on compact routing. In Workshop on Peer-to-Peer, Routing in Complex Graphs, and Network Coding, March 2007. See web pages here.

  18. Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 2007. to appear, See [BG05b] for the conference version.

  19. F. Bazzaro, M. Montassier, and A. Raspaud. (d,1)-total labeling of planar graphs with large girth and high maximum degree. Discrete Mathematics, 307:2141-2151, 2007.

  20. M. Montassier, A. Raspaud, and W. Wang. Acyclic 5-choosability of planar graphs without small cycles. Journal of Graph Theory, 54:245-260, 2007.

  21. Cyril Gavoille and Christophe Paul. Optimal distance labeling for interval graphs and related graphs families. SIAM Journal on Discrete Mathematics, 2007. To appear, see [GP03] for the conference version.

  22. G. Fertin and A. Raspaud. L(p,q) labeling of d-dimensional grids. Discrete Mathematics, 307(16):2132-2140, 2007.

  23. Tamar Eilam, Cyril Gavoille, and David Peleg. Average stretch analysis of compact routing schemes. Discrete Applied Mathematics, 155:598-610, January 2007. Appears also as RR-1195-98 (1998).

  24. Yon Dourisboure and Cyril Gavoille. Tree-decompositions with bags of small diameter. Discrete Mathematics, 307(16):2008-2029, 2007. Extended abstract published in EUROCOMB '03. Appears also as RR-1326-01 (2004).

  25. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Theoretical Computer Science, 2007. To appear, see [DG06] for the conference version.

  26. M. Chen, A. Raspaud, and W. Wang. Three-coloring planar graphs without short cycles. Information Processing Letters, 101:134-138, 2007.



2006

  1. Frédéric Ferchaud. étude des zones d'absorption dans la gestion du flux du trafic aérien. PhD thesis, Université Bordeaux 1, Talence, France, December 2006.

  2. Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strongly-bounded sparse decompositions of minor free graphs. Technical Report MSR-TR-2006-192, Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com, December 2006. See [AGMW07] for the conference version.

  3. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Schéma d'étiquetage d'adjacence pour les arbres de degrés borné. In 8èmes Journées Graphes et Algorithmes, November 2006.

  4. Cyril Gavoille. An overview on compact routing. In 2nd Research Workshop on Flexible Network Design, October 2006. See web pages here.

  5. Cyril Gavoille. Distributed data structures: A survey on informative labeling schemes (invited talk). In R. Královic and P. Urzyczyn, editors, 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 4162 of Lecture Notes in Computer Science, page 38. Springer, August 2006.

  6. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs: Upper bounds. In 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 207-216. ACM Press, July 2006. Slides available here.

  7. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs: Lower bounds. In 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 217-224. ACM Press, July 2006. Slides available here.

  8. Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. In 26th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society Press, July 2006. See [AGGM05] for the TR version. Slides available here: .ppt and .pdf.

  9. Pierre Fraigniaud and Cyril Gavoille. Header-size lower bounds for end-to-end communication in memoryless networks. Computer Networks, 50(10):1630-1638, July 2006. Selected paper for the DISC '03 Special Issue.

  10. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. In 13th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 4056 of Lecture Notes in Computer Science, pages 100-114. Springer, July 2006. See [DG07b] for the journal version. Appears also as RR-1388-06 (2006). Slides available here.

  11. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Short labels by traversal and jumping. In 13th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 4056 of Lecture Notes in Computer Science, pages 143-156. Springer, July 2006. Appears also as RR-1389-06 (2006).

  12. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Adjacency labeling for bounded degree trees and applications. In 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, July 2006. Dedicated to Jarik Nesetril on the occasion of his 60th birthday.

  13. Ittai Abraham and Cyril Gavoille. Object location using path separators. In 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 188-197. ACM Press, July 2006. Slides available here.

  14. L. Esperet and A. Pinlou. Acyclic improper choosability of outerplanar graphs. Research Report RR-1405-06, LaBRI, Université Bordeaux 1, 351 Cours de la Libération, 33405 Talence Cedex, France, may 2006.

  15. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks even small worlds. Distributed Computing, 18(4):279-291, March 2006. Appears also in PODC '04.

  16. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Short labels by traversal and jumping. Research Report RR-1389-06, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2006. Extended abstract published in SIROCCO '06.

  17. Ittai Abraham and Cyril Gavoille. Object location using path separators. Research Report RR-1394-06, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2006. Extended abstract published in PODC '06.

  18. Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners. Research Report RR-1388-06, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2006. Extended abstract published in SIROCCO '06.

  19. A. Pêcher and X. Zhu. On the circular chromatic number of circular partitionable graphs. J. of Graph Theory, 2006. accepted.

  20. A. Pêcher and A. Wagler. On non-rank facets in stable set polytopes of webs with clique number four. Discrete Applied Math., 154(9):1408-1415, 2006.

  21. A. Pêcher and A. Wagler. A construction for non-rank facets of stable set polytopes of webs. European J. of Comb., 2006. accepted.

  22. A. Pêcher and A. Wagler. Almost all webs are not rank-perfect. Math. prog., 105(2-3):311-328, 2006.

  23. A. Pinlou and É. Sopena. Oriented vertex and arc colorings of outerplanar graphs. Inform. Process. Lett., 100, 2006.

  24. A. Pinlou and É. Sopena. The acircuitic directed star arboricity of subcubic graphs is at most four. Discrete Math., 306, 2006.

  25. A. Pinlou. On oriented arc-coloring of subcubic graphs. Elect. J. Comb., 13(1), 2006.

  26. M. Montassier, A. Raspaud, and W. Wang. Acyclic 4-choosability of planar graphs without cycles of specific lengths. Algorithms and Combinatorics, Springer, 26:473-491, 2006.

  27. M. Montassier and A. Raspaud. (d,1)-total labeling of graphs with a given maximum average degree. J. of Graph Theory, 51:93-109, 2006.

  28. E. Mácajová and A. Raspaud. On the strong circular 5-flow conjecture. J. of Graph Theory, 52:307-316, 2006.

  29. D. Gonçalves, A. Raspaud, and M.A. Shalu. On oriented labelling parameters. Formal Models, Languages and Applications,World Scientific, Singapore, 66:33-45, 2006.

  30. M. DeVos, J. Nesetril, and A. Raspaud. On edge-maps whose inverse preserves flows or tensions. in Graph Theory in Paris (Proceedings of a Conference in Memory of Claude Berge), Trends in Mathematics, Birkhäuser, Basel, pages 109-138, 2006.

  31. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. Graphs and Combinatorics, 22(2):185-202, 2006. Extended abstract published in WG '04.

  32. Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. Technical Report MSR-TR-2005-175, Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com, December 2005. See [AGGM06] for the conference version.

  33. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs for compact routing schemes. Research Report RR-1374-05, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 2005.

  34. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. Research Report RR-1330-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, July 2004. Extended abstract published in DISC '04.



2005

  1. Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. In 16th Annual International Symposium on Algorithms and Computation (ISAAC), volume 3827 of Lecture Notes in Computer Science, pages 1122-1131. Springer, December 2005. See [BG07] for the journal version.

  2. Cyril Gavoille and Olivier Ly. Distance labeling in hyperbolic graphs. In 16th Annual International Symposium on Algorithms and Computation (ISAAC), volume 3827 of Lecture Notes in Computer Science, pages 1071-1079. Springer, December 2005. Slides available here.

  3. Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. Technical Report MSR-TR-2005-175, Microsoft Research, Microsoft Corporation, One Microsoft Way, Redmond, WA 98052 - http://www.research.microsoft.com, December 2005. See [AGGM06] for the conference version.

  4. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs for compact routing schemes. Research Report RR-1374-05, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 2005.

  5. Fabrice Bazzaro and Cyril Gavoille. Distance labeling for permutation graphs. In Elsevier, editor, 7th International Conference on Graph Theory (ICGT), volume 22, pages 461-467. Electronic Notes in Discrete Mathematics, October 2005. Slides available here, and See [BG07] for the journal version.

  6. S. Coulonges, A. Pêcher, and A. Wagler. On stable set polytopes of circular-perfect graphs. In ALIO/EURO V conference on combinatorial optimization, October 2005. talk by S. Coulonges.

  7. Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Edge partition of toroidal graphs into forests in linear time. In Elsevier, editor, 7th International Conference on Graph Theory (ICGT), volume 22, pages 421-425. Electronic Notes in Discrete Mathematics, October 2005. Slides available here.

  8. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In 19th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 442-456. Springer, September 2005. Slides available here.

  9. S. Coulonges, A. Pêcher, and A. Wagler. On strongly circular-perfectness. In ICGT'05 - 7th International Colloquium on Graph Theory, volume 22 of Electron. Notes Discrete Math., pages 369-374. Elsevier, September 2005. talk by S. Coulonges.

  10. Cyril Gavoille. Distributed data structures: A survey I & II. In 8th Seminar on Optimization and Decision Aid (SODA), France Télécom R&D Division, June 2005. Program.

  11. Cyril Gavoille. Distributed data structures: A survey (invited talk). In 12th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 3499 of Lecture Notes in Computer Science, page 2. Springer, May 2005. Slides available here.

  12. S. Coulonges, A. Pêcher, and A. Wagler. On the imperfection ratio of a-perfect graphs and some consequences. In CTW'05 - Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2005. LaBRI Research Report RR-1359-05.

  13. Cyril Gavoille. Étiquetage des graphes. In École Jeunes Chercheurs en Algorithmique et Calcul Formel - École thématique CNRS 05 13 051, April 2005. See http://www.lirmm.fr/~ejc2005.

  14. Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. Research Report RR-1343-05, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2005.

  15. Fabrice Bazzaro. Etiquetage de graphes : codage et coloration. PhD thesis, LaBRI (Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux 1), 2005.

  16. F. Bazzaro, M. Montassier, and A. Raspaud. (d,1)-total labelling of planar graphs with large girth and high maximum degree. Discrete Mathematics, 2005. To appear.

  17. F. Bazzaro, M. Montassier, and A. Raspaud. (d,1)-total labelling of planar graphs with large girth and high maximum degree. Discrete Math., 2005. To appear.

  18. F. Bazzaro and C. Gavoille. Localized and compact data-structure for comparability graphs. Technical Report RR-1343-05, LaBRI, 2005.

  19. A. Pêcher, A. Wagler, and X. Zhu. Three classes of minimal circular imperfect graphs. In Proceedings of GRACO2005, volume 19 of Electron. Notes Discrete Math., pages 9-15, Rio de Janeiro, Brazil, 2005. Elsevier.

  20. M. Montassier, A. Raspaud, and W. Wang. Bordeaux 3-color conjecture and 3-choosability. Technical Report RR-1367-05, LaBRI, 2005.

  21. M. Montassier, A. Raspaud, and W. Wang. Acyclic 5-choosability of planar graphs without small cycles. Technical Report RR-1366-05, LaBRI, 2005.

  22. M. Montassier, A. Raspaud, and W. Wang. Acyclic 4-choosability of planar graphs without cycles of specific lengths. Technical Report RR-1365-05, LaBRI, 2005.

  23. M. Montassier and A. Raspaud. A note on 2-facial coloring of plane graphs. Technical Report RR-1341-05, LaBRI, 2005.

  24. M. Montassier and A. Raspaud. A note on 2-facial coloring of plane graphs. Information Processing Letters, 2005. To appear.

  25. M. Montassier and A. Raspaud. (d,1)-total labelling of graphs with a given maximum average degree. Journal of Graph Theory, 2005. To appear.

  26. M. Montassier, P. Ochem, and A. Raspaud. On the acyclic choosability of graphs. Journal of Graph Theory, 2005. To appear.

  27. M. Montassier. A smaller not 3-choosable planar graph without 4- and 5-cycles. Technical Report RR-1361-05, LaBRI, 2005.

  28. M. Montassier. A note on the not 3-choosability of some families of planar graphs. Information Processing Letters, 2005. To appear.

  29. M. Montassier. Acyclic 4-choosability of planar graphs with girth at least 5. GT04 special volume in memory of Claude Berge, 2005. To appear.

  30. E. Mácajová, A. Raspaud, and M. Skoviera. Abelian colourings of cubic graphs. In 7th International Colloquium on Graph Theory (ICGT'05), volume 22 of Electronic Notes on Discrete Mathematics, pages 333-339. Elsevier, 2005.

  31. M. Hosseini Dolama and E. Sopena. On the oriented chromatic number of halin graphs. Inform. Proc. Letters, 2005. to appear.

  32. D. Gonçalves and M. Montassier. Acyclic choosability of graphs with small maximum degree. Technical Report RR-1348-05, LaBRI, 2005.

  33. Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. Theoretical Computer Science, 333(3):415-432, 2005. An extended abstract appears in SIROCCO '03 (invited for the Sirocco special issue).

  34. D. Amar, E. Flandrin, G. Gancarzewicz, and A.P. Wojda. Bipartite graphs with every matching in a cycle. Discrete Math., 2005. To appear.

  35. D. Amar, E. Flandrin, and G. Gancarzewicz. Cyclability in bipartite graphs, 2005. Submitted.

  36. Cyril Gavoille and Nicolas Hanusse. On compact encoding of pagenumber k graphs. Discrete Mathematics & Theoretical Computer Science, 2005. To appear.

  37. D. Amar, D. Brito, and O. Ordaz. Hamiltonian cycles and hamiltonian biconnectedness in bipartite digraph. Divulgacines Matematicas, 2005. To appear.

  38. G. Fertin and A. Raspaud. Acyclic coloring of graphs of maximum degree \Delta . In Stefan Felsner, editor, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), volume AE of DMTCS Proceedings, pages 389-396. Discrete Mathematics and Theoretical Computer Science, 2005.

  39. L. Esperet, M.Montassier, and A. Raspaud. Linear choosability of graphs. In Stefan Felsner, editor, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), volume AE of DMTCS Proceedings, pages 99-104. Discrete Mathematics and Theoretical Computer Science, 2005.

  40. Yon Dourisboure and Cyril Gavoille. Tree-decompositions with bags of small diameter. Discrete Math, 2005. to appear.

  41. Yon Dourisboure. Compact routing schemes for generalised chordal graphs. Journal of Graph Algorithms and Applications, 2005. to appear.

  42. Olivier Delmas, Frédéric Havet, Mickaël Montassier, and Stéphane Pérennes. Design of fault tolerant on-board networks. Research report RR 1345-05, Laboratoire bordelais de recherche en informatique (LaBRI), Unité Mixte de Recherche CNRS (UMR 5800), 2005.

  43. S. Coulonges, A. Pêcher, and A.K. Wagler. Polytope des stables des graphes fortement circulaires-parfaits. JPOC2 - Deuxièmes Journées Polyèdres et Optimisation Combinatoire, Marseille - talk by S. Coulonges, 2005.

  44. S. Coulonges, A. Pêcher, and A.K. Wagler. On the imperfection ratio of a-perfect webs. 8th Combinatorial Optimization Workshop, Aussois - talk by A.K. Wagler, 2005.

  45. S. Coulonges, A. Pêcher, and A.K. Wagler. Graphes fortement circulaires-parfaits sans triangles. JPOC2 - Deuxièmes Journées Polyèdres et Optimisation Combinato ire, Marseille, 2005.

  46. S. Coulonges, A. PÃcª¿½her, and A.K. Wagler. Triangle free strongly circular-perfect graphs. Eurocomb'05, poster, 2005.

  47. O.V. Borodin, A.N. Glebov, A. Raspaud, and M.R. Salavatipour. Planar graphs without cycles of length from 4 to 7 are 3-colorable. J. Combin. Theory Ser. B., 93:303-311, 2005.

  48. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. Journal of Graph Algorithms and Applications, 9(2):185-204, 2005. Appears also as RR-1295-03 (2003).



2004

  1. Frédéric Ferchaud, Vu Duong, Cyril Gavoille, and Mohamed Mosbah. Reducing disturbances by using absorption areas. In 1st International Conference on Research in Air Transportation (ICRAT), pages 111-115, November 2004.

  2. Fabrice Bazzaro and Cyril Gavoille. Etiquetage de distance des graphes de permutation. In E. Duchène et S. Gravier, editor, 6èmes Journées Graphes et Algorithmes, pages 22-24. Les Cahiers du laboratoire Leibniz, No 114, October 2004.

  3. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. In 18th International Symposium on Distributed Computing (DISC), volume 3274 of Lecture Notes in Computer Science, pages 305-319. Springer, October 2004. The full version appears in RR-1330-04 (2004).

  4. Vu Duong, Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. Using absorption areas to improve ATFM. In 23rd IEEE International Digital Avionics Systems Conference (DASC), October 2004.

  5. Vu Duong, Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. A new slot allocation for ATFM. In 7th IEEE International Conference on Intelligent Transportation Systems (ITSC), pages 1075-1079, October 2004.

  6. Yon Dourisboure. Compact routing schemes for tree-length \delta graphs and for k-chordal graphs. In 18-th International Symposium on DIStributed Computing (DISC 2004), volume 3274 of Lecture Notes in Computer Science, pages 365-378. Springer, October 2004.

  7. A. Pêcher and A. Wagler. Almost all webs are not rank-perfect. XXXV Annual Conference of the Operational Research Society of Italy - talk by A. Wagler, septembre 2004.

  8. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. Research Report, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 2004. Extended abstract published in WG '04. Appears also as Graphs and Combinatorics.

  9. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. Research Report RR-1330-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, July 2004. Extended abstract published in DISC '04.

  10. M. Montassier, P. Ochem, and A. Raspaud. On the acyclic choosability of graphs. In GTO4 Graph Theory 2004: a conference in memory of Claude Berge, Paris, July 2004.

  11. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks even small worlds. In 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 169-178. ACM Press, July 2004. Appears also in Journal of Distributed Computing for the PODC '04 Special Issue. Appears also as LRI-1376 (2003).

  12. Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup. Compact name-independent routing with minimum stretch. In 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 20-24. ACM Press, July 2004. Updated version here, and slides available here.

  13. G. Fertin, A. Raspaud, and O. Sýkora. No-hole l(p,0)-labelling of cycles, grids and hypercubes. In Ratislav Kralovic and Ondrej Sýkora, editors, 11th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 3104 of Lecture Notes in Computer Science, pages 138-148. Springer-Verlag, June 2004.

  14. Yon Dourisboure and Cyril Gavoille. Sparse additive spanners for bounded tree-length graphs. In 11th International Colloquium on Structural Information & Communication Complexity (SIROCCO), volume 3104 of Lecture Notes in Computer Science, pages 123-137. Springer, June 2004. See [DDGY07] for the journal version. Appears also as RR-1316-04 (2004).

  15. Yon Dourisboure and Cyril Gavoille. Sparse additive spanners for bounded tree-length graphs. In 11th Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 3104 of Lecture Notes in Computer Science, pages 123-137. Springer, June 2004.

  16. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, and Gilles Schaeffer. Planar graphs, via well-orderly maps and trees. In 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 3353 of Lecture Notes in Computer Science. Springer, June 2004. 270-284, A revised version is available as RR-1333-04. Appears also as Graphs and Combinatorics.

  17. F. Bazzaro and M. Montassier. Assignation de fréquences et étiquetage (d,1)-total dans les topologies planaires. In 6ème Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (ALGOTEL 2004), pages 27-31, Batz-sur-mer, France, 26-28 mai 2004. Institut National de Recherche en Informatique et Automatique.

  18. F. Bazzaro and M. Montassier. Assignation de fréquences et étiquetage (d,1)-total dans les topologies planaires. In 6ème Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (ALGOTEL 2004), pages 27-31, Batz-sur-mer, France, 26-28 mai 2004. Institut National de Recherche en Informatique et Automatique.

  19. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclectisme dans les petits mondes. In 6èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2004. Apparaît aussi dans LRI-1376 (2003).

  20. Yon Dourisboure and Cyril Gavoille. Small diameter bag tree-decompositions. Research Report RR-1326-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, May 2004. An updated version appears in Discrete Mathematics. Appears also as EUROCOMB '03.

  21. Yon Dourisboure and Cyril Gavoille. Sparse additive spanners for bounded tree-length graphs. Research Report RR-1316-04, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2004. An extended abstract appears in SIROCCO '04.

  22. G. Blin, G. Fertin, and S. Vialette. New results for the 2-interval problem. In Proc. Fifteenth Annual Combinatorial Pattern Matching Symposium (CPM 2004), volume 3109 of Lecture Notes in Computer Science, pages 311-322. Springer-Verlag, 2004.

  23. G. Blin, G. Fertin, R. Rizzi, and S. Vialette. Pattern matching in arc-annotated sequences: New results for the APS problem. Technical report, LINA, Université de Nantes, 2004. Submitted for publication.

  24. G. Blin, C. Chauve, and G. Fertin. The breakpoint distance for signed sequences. In Proc. 1st International Conference on Algorithms and Computational Methods for Biochemical and Evolutionary Networks(CompBioNets 2004). King's College London, 2004. To appear.

  25. József Balogh, Pascal Ochem, and András Pluhár. On the interval number of special graphs. J. Graph Theory., 46 (4):241-253, 2004.

  26. A. Pêcher, A.K. Wagler, and X. Zhu. Quelques familles de graphes minimaux imparfaits circulaires. 6èmes Journées Graphes et Algorithmes, Grenoble, Les Cahiers du laboratoire Leibniz, 2004.

  27. A. Pêcher. Cayley partitionable graphs and near-factorizations of finite groups. Discrete Math., 276(1-3):295-311, 2004. 6th International Conference on Graph Theory.

  28. Pascal Ochem. Oriented colorings of triangle-free planar graphs. Inf. Process. Lett., 92(2):71-76, 2004.

  29. Pascal Ochem. A generator of morphisms for infinite words. In Proceedings of the Workshop on Words avoidability, complexity and morphisms - Edited by G. Richomme, 2004.

  30. M. Montassier and O. Serra. Acyclic choosability and probabilistic methods. Technical report, 2004. Manuscript.

  31. M. Montassier, P. Ochem, and A. Raspaud. On the acyclic choosability of graphs. Technical Report RR-1335-04, LaBRI, 2004.

  32. M. Montassier. On acyclic choosability of planar graphs with large girth. Technical Report RR-1336-04, LaBRI, 2004.

  33. Lucian Ilie, Pascal Ochem, and Jeffrey Shallit. A generalization of repetition threshold. In MFCS, pages 818-826, 2004.

  34. M. Hosseini Dolama, E. Sopena, and X. Zhu. Incidence coloring of k-degenerated graphs. Discrete Math., 283:121-128, 2004.

  35. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. Appears also as RR-1239-00 (2000), and in SODA '01. Another link is available here.

  36. G. Fertin, A. Raspaud, and O. Sýkora. No-hole L(p,0) labelling of grids, tori and hypercubes. In Proc. 11th International Colloquium on Structural Information and Communication Complexity (SIROCCO '04), volume 3104 of Lecture Notes in Computer Science, pages 138-148. Springer-Verlag, 2004.

  37. G. Fertin, A. Raspaud, and O. Sýkora. No-hole L(p,0) labelings. In 6èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel '04). INRIA, 2004. To appear.

  38. G. Fertin, A. Raspaud, and B. Reed. Star coloring of graphs. Journal of Graph Theory, 47, No.3:163-182, 2004.

  39. G. Fertin, A. Raspaud, and B. Reed. On star coloring of graphs. Journal of Graph Theory, 47(3):163-182, 2004.

  40. G. Fertin and A. Raspaud. A survey of Knödel graphs. Discrete Applied Mathematics, 137(2):173-195, 2004.

  41. G. Fertin and A. Raspaud. L(p,q) labeling of d-dimensional grids. Discrete Mathematics, 2004. To appear.

  42. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory of Computing Systems, 37:441-456, 2004. Appears also as IT-C Series 2001-6 (2001), and an extended abstract appears in SPAA '02.

  43. M. DeVos, J. Nesetril, and A. Raspaud. Antisymmetric flows and edge-connectivity. Discrete Mathematics, 276:161-167, 2004.

  44. F. Comellas, G. Fertin, and A. Raspaud. Recursive graphs with small-world scale-free properties. Physical Review E, Brief Notes, 69-037104, 2004.

  45. F. Comellas, G. Fertin, and A. Raspaud. Recursive graphs with small-word scale-free properties. Physical Review E, 69:037104-1,037104-4, 2004.

  46. C. Chauve and G. Fertin. On maximal instances for the original syntenic distance. Theoretical Computer Science, 326:29-43, 2004.

  47. Richard Castanet, Cyril Gavoille, Mohamed Mosbah, and Frédéric Ferchaud. Utilisation des zones d'absorption pour améliorer la gestion de flux du trafic aérien. Rapport de contrat (intermédiaire) marché C/1.291/CE/NB/03/, LaBRI, Université Bordeaux 1 - ENSEIRB, January 2004.



2003

  1. Frédéric Ferchaud, Cyril Gavoille, and Mohamed Mosbah. Using absorption areas to improve ATFM. In ERC Innovative Research Workshop, December 2003.

  2. Richard Castanet, Cyril Gavoille, Mohamed Mosbah, and Frédéric Ferchaud. Gestion de flux du traffic aérien en intra et inter réseaux : un modèle de graphes évolutifs, November 2003.

  3. Pierre Fraigniaud, Cyril Gavoille, and Christophe Paul. Eclecticism shrinks the world. Research Report LRI-1376, LRI, Université Paris-Sud, 91405 Orsay cedex, France, October 2003. Extended abstract published in PODC '04.

  4. Pierre Fraigniaud and Cyril Gavoille. Lower bounds for oblivious single-packet end-to-end communication. In 17th International Symposium on Distributed Computing (DISC), volume 2848 of Lecture Notes in Computer Science, pages 211-223. Springer, October 2003. Appears also as RR-1289-03 (2003), and a revised version appears in Computer Networks.

  5. A. Pêcher and A. Wagler. A construction for non-rank facets of stable set polytopes of webs. In Eurocomb'03, pages 301-305, September 2003. full version accepted in European J. of Comb.

  6. Cyril Gavoille and Christophe Paul. Optimal distance labeling schemes for interval and circular-arc graphs. In G. Di Battista and U. Zwick, editors, 11th Annual European Symposium on Algorithms (ESA), volume 2832 of Lecture Notes in Computer Science, pages 254-265. Springer, September 2003. See [GP07] for the journal version. Appears also as RR-1290-03 (2003). Slides available here.

  7. Cyril Gavoille and Martin Nehéz. On interval routing in random meshes. In J. Fila, editor, 2nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pages 147-150, September 2003. A revised appears in Theoretical Computer Science.

  8. Yon Dourisboure and Cyril Gavoille. Tree-decomposition of graphs with small diameter bags. In J. Fila, editor, 2nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pages 100-104, September 2003. An updated version appears in Discrete Mathematics.

  9. Yon Dourisboure and Cyril Gavoille. Tree-decomposition of graphs with small diameter bags. In European conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2003), pages 100-104. ITI, September 2003.

  10. Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. In 9th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 149-164. Carleton University Press, June 2003. Appears also as RR-1294-03 (2003), and a revised appears in Theoretical Computer Science.

  11. F. Comellas, G. Fertin, and A. Raspaud. Vertex labeling and routing in recursive clique-trees, a new family of small-world scale-free graphs. In Jop Sibeyn, editor, 10th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 73-87. Carleton University Press, June 2003.

  12. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. In 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2880 of Lecture Notes in Computer Science, pages 81-92. Springer-Verlag, June 2003. Appears also as RR-1295-03 (2003), and an updated version appears in Journal of Graph Algorithms and Applications (2005).

  13. Jean-Claude Bermond, Olivier Delmas, Frédéric Havet, Mickaël Montassier, and Stéphane Pérennes. Réseaux de télécommunication minimaux embarqués tolérants aux pannes. In 5ème Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (ALGOTEL 2003), pages 27-32, Banyuls-sur-mer, France, 12-14 mai 2003. Institut National de Recherche en Informatique et Automatique. ISBN 2-7261-1246-3.

  14. Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed Computing, 16:111-120, May 2003. PODC 20-Year Special Issue, Appears also as RR-1261-01 (2001).

  15. A. Pêcher and X. Zhu. Colorations circulaires des graphes circulaires partitionnables. Journées GRAAL, Dijon, avril 2003.

  16. A. Pêcher and A. Wagler. Almost all webs are not rank-perfect. 7th Combinatorial Optimization Workshop, Aussois, mars 2003.

  17. Cyril Gavoille and Martin Nehéz. Interval routing in reliability networks. Research Report RR-1294-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2003. An extended abstract appears in SIROCCO '03, and a revised appears in Theoretical Computer Science.

  18. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. Canonical decomposition of outerplanar maps and application to enumeration, coding and generation. Research Report RR-1295-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, March 2003. An extended abstract appears in WG '03, and an updated version appears in Journal of Graph Algorithms and Applications (2005).

  19. Cyril Gavoille and Christophe Paul. Small universal distance matrices. Research Report RR-1290-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2003. An extended abstract appears in ESA '03. A revised version is available here.

  20. Pierre Fraigniaud and Cyril Gavoille. Lower bounds for oblivious single-message end-to-end communication. Research Report RR-1289-03, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2003. An extended abstract appears in DISC '03, and a revised version appears in Computer Networks.

  21. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. An information-theoretic upper bound of planar graphs using triangulation. In 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2607 of Lecture Notes in Computer Science, pages 499-510. Springer, February 2003. Appears also as RR-1279-02 (2002), and a revised version is available here. Slides available here.

  22. G. Blin, G. Fertin, and S. Vialette. A polynomial algorithm for the 2-interval pattern problem. In Poster session of the 3rd Workshop on Algorithms in Bioinformatics (WABI 2003), 2003.

  23. G. Blin, G. Fertin, I. Rusu, and C. Sinoquet. RNA sequences and the EDIT(NESTED,NESTED) problem. Research Report RR-IRIN-03.07, IRIN, Université de Nantes, 2003. Submitted for publication.

  24. F. Bazzaro, M. Montassier, and A. Raspaud. (d,1)-total labelling of planar graphs with large girth and high maximum degree. Technical Report RR-1307-03, LaBRI, 2003.

  25. F. Bazzaro, M. Montassier, and A. Raspaud. (d,1)-total labelling of connected planar graphs with large girth and high maximum degree. Technical Report RR-1307-03, LaBRI, 2003.

  26. A. Pêcher and A. K. Wagler. La plupart des webs ne sont pas rang-parfaits. Journées Polyèdres et Optimisation Combinatoire JPOC, Clermont-Ferrand, 2003.

  27. A. Pêcher and A. Wagler. On non-rank facets in stable set polytopes of webs with clique number four. In Electronic Notes in Discrete Mathematics, volume 13, pages 96-99. 2nd Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2003. full version accepted in Discrete Applied Mathematics.

  28. A. Pêcher. A note on the circular chromatic number of circular perfect planar graphs. LaBRI Research Report RR-1309-03, 2003.

  29. Arnaud Pêcher. Partitionable graphs arising from near-factorizations of finite groups. Discrete Math., 269(1-3):191-218, 2003.

  30. M. Montassier and A. Raspaud. (d,1)-total labelling of graphs with a given maximum average degree. Technical Report RR-1308-03, LaBRI, 2003.

  31. M. Montassier. Observability of recursive clique-trees. In Eurocomb03. European conference on Combinatorics, Graph Theory and Applications, pages 275-279, Prague, September 8 - 12, 2003.

  32. Gregory Kucherov, Pascal Ochem, and Michaël Rao. How many square occurrences must a binary sequence contain?Electr. J. Comb., 10, 2003.

  33. Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. Journal of Discrete Algorithms, 1(2):237-254, 2003. Extended abstract published in SIROCCO '00. Appears also as RR-1233-00 (2000).

  34. Cyril Gavoille and Christophe Paul. Distance labeling scheme and split decomposition. Discrete Mathematics, 273(1-3):115-130, 2003. Extended abstract published in COMB '01. Appears also as RR-1263-01 (2001).

  35. G. Fertin, A. Raspaud, and A. Roychowdhury. On the oriented chromatic number of grids. Information Processing Letters, 85:261-266, 2003.

  36. G. Fertin, A. Raspaud, and A. Roychowdhury. On the oriented chromatic number of grids. Information Processing Letters, 85(5):261-266, 2003.

  37. G. Fertin and A. Raspaud. A survey on Knödel graphs. Discrete Applied Mathematics, 137(2):173-195, 2003.

  38. G. Fertin and A. Raspaud. L(p,q) labeling of d-dimensional grids. In Proc. Euroconference on Combinatorics, Graph Theory and Applications (EUROCOMB'03), 2003.

  39. G. Fertin, A.L. Liestman, T.C. Shermer, and L. Stacho. Edge-disjoint spanners in cartesian products of graphs. Technical report, Simon Fraser University, Vancouver, Canada, 2003. Submitted for publication.

  40. G. Fertin, E. Godard, and A. Raspaud. Acyclic and k-distance coloring of the grid. Information Processing Letters, 87:51-58, 2003.

  41. G. Fertin, E. Godard, and A. Raspaud. Acyclic and k-distance coloring of the grid. Information Processing Letters, 87(1):51-58, 2003.

  42. Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Journal of Algorithms, 46(2):97-114, 2003. Extended abstract published in PODC '98. Appears also as RR-1195-98 (1998).

  43. Yon Dourisboure. Routage compact et longueur arborescente. PhD thesis, Université Bordeaux 1, 2003.

  44. N. Alon, G. Fertin, A.L. Liestman, T.C. Shermer, and L. Stacho. Factor d-domatic colorings of graphs. Discrete Mathematics, 262(1-3):17-25, 2003.

  45. F. Comellas, G. Fertin, and A. Raspaud. Vertex labeling and routing in recursive clique-trees, a new family of small-world scale-free graphs. In Proc. 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO '03), volume 17 of Proceedings in Informatics, pages 73-87. Carleton Scientific, 2003.

  46. C. Chauve and G. Fertin. On maximal instances for the original syntenic distance. In Proc. 2nd European Conference on Computational Biology (ECCB 2003) - Short Papers and Posters, pages 285-286. INRIA, 2003.

  47. O.V. Borodin and A. Raspaud. A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B., 88:17-27, 2003.



2002

  1. Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. In 16th International Symposium on Distributed Computing (DISC), volume 2508 of Lecture Notes in Computer Science, pages 252-264. Springer, October 2002. An updated version is available here. Appears also as RR-1274-02 (2002).

  2. Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. In 16-th International Symposium on DIStributed Computing (DISC 2002), volume 2508 of Lecture Notes in Computer Science, pages 252-264. Springer-Verlag, October 2002.

  3. Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse. An information upper bound of planar graphs using triangulation. Research Report RR-1279-02, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 2002. Extended abstract published in STACS '03, and a revised version is available here.

  4. A. Pêcher and A. Wagler. How imperfect are webs and antiwebs. XXXIII Annual Conference of the Operational Research Society of Italy - talk by A. Wagler, septembre 2002.

  5. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Nearest common ancestors: A survey and a new distributed algorithm. In 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 258-264. ACM Press, August 2002. Appears also as IT-C Series 2001-6 (2001), and in Theory of Computing Systems. Slides available here.

  6. D. Barth, O. Baudon, and J. Puech. Decomposable trees: a polynomial algorithm for tripodes. Discrete Applied Mathematics, 119(3):205-216, july 2002.

  7. P. Auillans. Toward topic maps processing and visualization. In Sixth International Conference on Information Visualisation (IV'02), London, England, July 2002.

  8. Yon Dourisboure. An additive stretched routing scheme for chordal graphs. In 28-th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '02), volume 2573 of Lecture Notes in Computer Science, pages 150-163. Springer-Verlag, June 2002.

  9. Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. Research Report RR-1274-02, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, May 2002. Extended abstract published in DISC '02.

  10. Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. In 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2285 of Lecture Notes in Computer Science, pages 65-75. Springer, March 2002. Slides available here.

  11. Jean-Claude Bermond, Éric Darrot, and Olivier Delmas. Design of fault-tolerant networks for satellites (TWTA redundancy). Networks, 40(4):202-207, 2002. Wiley InterScience.

  12. Pascal Auillans and Olivier Baudon. Topic maps et hypergraphes. In Yves Chiricota, editor, WVDR 2002, Montpellier, Janvier 2002.

  13. P. Auillans, P. Ossona de Mendez, P. Rosenstiehl, and B. Vatant. A formal model for topic maps. In Proceedings of the First International Semantic Web Conference on The Semantic Web, pages 69-83. Springer-Verlag, 2002.

  14. E. Sopena. There exist oriented planar graphs with oriented chromatic number at least sixteen. Inform. Proc. Letters, 81(6):309-312, 2002. (Compressed postcript).

  15. D. Fon-Der-Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena. Nilpotent families of endomorphisms of (p(v)^+,\cup). J. Combin. Theory, Ser. B, 86(1):100-108, 2002. (Compressed postcript).

  16. D. Fon-Der-Flaass, A.V. Kostochka, J. Ne setril, A. Raspaud, and E. Sopena. Nilpotent families of endomorphisms of (p(v)^+,\cup). J. Combin. Theory Ser. B., No. 86:100-108, 2002.

  17. G. Fertin, E. Godard, and A. Raspaud. Minimum feedback vertex set and acyclic coloring. Information Processing Letters, 84:131-139, 2002.

  18. G. Fertin, E. Godard, and A. Raspaud. Minimum feedback vertex set and acyclic coloring. Information Processing Letters, 84(3):131-139, 2002.

  19. G. Fertin, E. Godard, and A. Raspaud. Conversion de longueur d'onde dans les réseaux optiques - facteur d'optimalité \frac53. In 4èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel '02), pages 33-39. INRIA, 2002.

  20. Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Recognizing Knödel graphs. Discrete Mathematics, 250(1-3):41-62, 2002. Extended abstract published in WG '99. Appears also as RR-LRI-1238 (2000).

  21. O.V. Borodin, A.V. Kostochka, A. Raspaud, and E. Sopena. On the minimum number of colours in acyclic k-strong colorings of maps on surfaces. Matem. zametki (in Russian), 72, No. 1:35-37, 2002.

  22. O.V. Borodin, D. Fon-Der-Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena. Acyclic list 7-colouring of planar graphs. J. Graph Theory, 40(2):83-90, 2002. (Compressed postcript).

  23. O.V. Borodin, D. Fon-Der-Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena. Acyclic list 7-coloring of planar graphs. Journal of Graph Theory, 40, No. 2:83-90, 2002.



2001

  1. Pascal Auillans, Olivier Baudon, and Franck Jarry. Using xml-topic map on a pda. In Jane Harnad, editor, XML 2001-US, Orlando, December 2001.

  2. P. Auillans, O. Baudon, and F. Jarry. Using xml-topic map on a pda. In Pamela Gennusa, editor, XML 2001-US, Orlando, December 2001.

  3. Cyril Gavoille. A note on implicit representation of graphs. Research Report RR-1268-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, December 2001.

  4. Cyril Gavoille and Christophe Paul. Split decomposition and distance labelling: An optimal scheme for distance hereditary graphs. In Marc Noy Jaroslav Nesetril and Oriol Serra, editors, European Conference on Combinatorics, Graph Theory and Applications (COMB), volume 10, pages 117-120. Electronic Notes in Discrete Mathematics, November 2001. For a version with references, click here. A long version appears in Discrete Mathematics, and also as RR-1263-01 (2001).

  5. Cyril Gavoille and Christophe Paul. Distance labeling scheme and split decomposition. Research Report RR-1263-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 2001. An updated version appears in Discrete Mathematics, and an extended abstract appears in COMB '01.

  6. O. Baudon, G. Fertin, and I. Havel. Routing permutations in the hypercube. Discrete Applied Mathematics, 113(1):43-58, September 2001.

  7. Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. Research Report RR-1262-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 2001. Extended abstract published in STACS '02.

  8. Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Research Report RR-1261-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, August 2001. Appears also in Journal of Distributed Computing for the PODC 20-Year Special Issue.

  9. Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. In F. Meyer auf der Heide, editor, 9th Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science, pages 476-488. Springer, August 2001. Appears also as RR-1250-00 (2000).

  10. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Identifying nearest common ancestors in a distributed environment. Technical Report IT-C Series 2001-6, ISSN 1600-6100, The IT University of Copenhagen, August 2001. Extended abstract published in SPAA '02, and in Theory of Computing Systems.

  11. Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. Distributed Computing, 14:217-229, July 2001. Extended abstract published in PODC '00. Appears also as LRI-1241 (2000).

  12. Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, 28th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757-772. Springer, July 2001. Slides available here.

  13. Cyril Gavoille, David Peleg, André Raspaud, and Eric Sopena. Small k-dominating sets in planar graphs with applications. In 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 2204 of Lecture Notes in Computer Science, pages 201-216. Springer, June 2001. A revised version is available here.

  14. Cyril Gavoille. Compact and distributed data structures (invited lecture). In IWIN-SIROCCO '01 joint conference, June 2001. Slides available here.

  15. P. Auillans and O. Baudon. Graph clustering for very large topic maps. In Pamela Gennusa, editor, XML 2001-Europe, Berlin, May 2001.

  16. Cyril Gavoille, David Peleg, André Raspaud, and Eric Sopena. Small k-dominating sets in planar graphs with applications. Research Report RR-1258-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, May 2001. Extended abstract published in WG '01, and a revised version is available here.

  17. Pierre Fraigniaud and Cyril Gavoille. Comment router dans un arbre ?. In 3èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 85-88. INRIA, May 2001. Slides available here.

  18. Yon Dourisboure and Cyril Gavoille. Interval routing for generalized Hypercube-like graphs. In 3èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 61-68. INRIA, May 2001.

  19. Yon Dourisboure and Cyril Gavoille. Interval routing for generalized Hypercube-like graphs. In 3e Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 61-68. INRIA, May 2001.

  20. Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column, 32(1):36-52, March 2001.

  21. Bruno Beauquier, Olivier Delmas, and Stéphane Pérennes. Tight bounds for broadcasting in the linear cost model. Journal of Interconnection Networks, 2(2-2001):175-188, 2001. World Scientific Publishing Company.

  22. O. Baudon, G. Fertin, and I. Havel. Routing permutations and 2-1 routing requests in the hypercube. Discrete Applied Mathematics, 113(1):43-58, 2001.

  23. E. Sopena. Two problems on planar graphs. In Proc. 5th Graph Theory Day, 2001. (Compressed postcript).

  24. E. Sopena. Oriented graph coloring. Discrete Math., 229(1-3):359-369, 2001. (Compressed postcript).

  25. P. Auillans and J. Delahousse. Knowledge index manager. In M. Jünger P. Mutzel and S. Leipert, editors, Graph Drawing, 9th International Symposium, pages 469-470. LNCS, 2001.

  26. A. Pêcher. Getting partitionable graphs from another one, by modifying only two maximum cliques. Technical report, I.A.S.I., 2001.

  27. J. Nesetril and E. Sopena. On the oriented game chromatic number. Electronic J. of Combin., 8(2), 2001. Paper 14, (Compressed postcript).

  28. D. Amar, A. Raspaud, and O. Togni. All-to-all wavelength-routing in all-optical compound networks. Discrete Math., 235:353-363, 2001.

  29. P. Hell, A.V. Kostochka, A. Raspaud, and E. Sopena. On nice graphs. Discrete Math., 234:39-51, 2001.

  30. M. Habib, C. Paul, and L. Viennot. Linear time recognition of p_4-indifference graphs. Discrete Mathematics and Theoretical Computer Science, 2001. To appear.

  31. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. In 12th Symposium on Discrete Algorithms (SODA), pages 210-219. ACM-SIAM, January 2001. Appears also as RR-1239-00 (2000), and an updated version appears in Journal of Algorithms. Slides available here.

  32. Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. SIAM Journal on Computing, 31(3):706-721, 2001. Extended abstract published in DISC '98. Appears also as RR-1202-98 (1998).

  33. Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61(5):679-687, 2001. Updated version of RR-1181-97 (1997).

  34. C. Gavoile, D. Peleg, A. Raspaud, and E. Sopena. Small k-dominating sets in planar graphs with applications. In Proc. Workshop on Graphs, WG'01, LNCS 2204, pages 201-216, 2001. (Compressed postcript).

  35. Pierre Fraigniaud and Cyril Gavoille. Routing in trees. Research Report RR-1252-01, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, January 2001. Extended abstract published in ICALP '01.

  36. D. Amar, M. El Kadi Abderrezzak, and E. Flandrin. Cyclability and pancyclability in bipartite graphs. Discrete Math., 236:3-11, 2001.

  37. G. Fertin, A. Raspaud, and B. Reed. On star coloring of graphs. In 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), volume 2204 of Lecture Notes in Computer Science, pages 140-153. Springer-Verlag, 2001.

  38. G. Fertin and A. Raspaud. Neighborhood communications in networks. In Proc. Euroconference on Combinatorics, Graph Theory and Applications (COMB'01), Electronic Notes on Discrete Mathematics, 2001.

  39. G. Fertin and A. Raspaud. k-neighborhood broadcasting. In 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2001), volume 11 of Proceedings in Informatics, pages 133-146. Carleton Scientific, 2001.

  40. O.V. Borodin, A.V. Kostochka, A. Raspaud, and E. Sopena. Acyclic coloring of 1-planar graphs. Discrete Applied Math., 114, No.1-3:29-41, 2001.

  41. O.V. Borodin, D. Fon-Der-Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena. On deeply critical oriented graphs. J. Combin. Theory, Ser. B, 81:150-155, 2001. (Compressed postcript).

  42. O.V. Borodin, D. Fon-Der-Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena. On deeply critical oriented graphs. J. Combin. Theory Ser. B., 81, No. 1:150-155, 2001.



2000

  1. A. Pêcher. Graphes de cayley partitionnables. PhD thesis, University of Orleans, France, December 2000.

  2. Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. Research Report RR-1250-00, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, December 2000. Extended abstract published in ESA '01.

  3. Cyril Gavoille. Structures de données compactes et distribuées, December 2000. Thèse d'habilitation à diriger les recherches, Université de Bordeaux, Slides available here.

  4. Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, and John Michael Robson. On recognizing Cayley graphs. In 8th Annual European Symposium on Algorithms (ESA), volume 1879 of Lecture Notes in Computer Science, pages 76-87. Springer, September 2000. Appears also as LRI-1242 (2000).

  5. Cyril Gavoille and Christophe Paul. Approximate distance labeling schemes. In Elsevier, editor, 6th International Conference on Graph Theory (ICGT), volume 5, pages 134-137. Electronic Notes in Discrete Mathematics, July 2000. Slides available here.

  6. Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. In 19th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20. ACM Press, July 2000. The full version appears in JDC. Appears also as LRI-1241 (2000).

  7. A. Raspaud, O. Sýkora, and I. Vrt'o. Congestion and dilatation, similarities and differences: a survey. In Michele Flammini, Enrico Nardelli, Guido Proietti, and Paul Spirakis, editors, 7th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 269-280. Carleton Scientific, June 2000.

  8. Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. In Michele Flammini, Enrico Nardelli, Guido Proietti, and Paul Spirakis, editors, 7th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 127-140. Carleton Scientific, June 2000. Extended abstract of RR-1233-00 (2000). An updated version is available in Journal of Discrete Algorithms. Slides available here.

  9. G. Fertin, A. Raspaud, H. Schröder, O. Sýkora, and I. Vrt'o. Diameter of the knödel graph. In 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '00), volume 1928 of Lecture Notes in Computer Science, pages 149-160. Springer-Verlag, June 2000.

  10. Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. Research Report RR-1239-00, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, April 2000. An updated version appears in Journal of Algorithms, and an extended abstract appears in SODA '01.

  11. Cyril Gavoille and Akka Zemmari. The compactness of adaptive routing tables. Research Report RR-1233-00, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 2000. Extended abstract published in SIROCCO '00, and an updated version is available in Journal of Discrete Algorithms.

  12. Jean-Claude Bermond, Éric Darrot, and Olivier Delmas. Design of fault-tolerant networks on satellites (TWTA redundancy). Research Report 1243-00, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Joint unit of the CNRS (UMR 5800), Université Bordeaux 1, France, 2000. Abstract.

  13. Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Recognizing abelian Cayley colored digraphs. Research Report LRI-1242, LRI, Université Paris-Sud, 91405 Orsay cedex, France, January 2000. Extended abstract of the updated version published in ESA '00.

  14. O. Togni. Placement de convertisseurs de longueur d'onde dans les réseaux optiques. In Proceedings of Algotel'00, 2000.

  15. O. Togni. Irregularity strength and compound graphs. Discrete Math., 218(1-3):235-243, 2000.

  16. André Raspaud. Proceedings of the Workshop ALTEC-KIT, Saarbrücken, May 1997, volume 245. Theoretical Computer Science, 2000.

  17. A. Pêcher. NFFinder, 2000.

  18. A. Pêcher. Cayley partitionable graphs. In 6th International Conference on Graph Theory (Marseille, 2000), volume 5 of Electron. Notes Discrete Math., page 4 pp. (electronic). Elsevier, Amsterdam, 2000.

  19. J. Nesetril and A. Raspaud. Colored homomorphisms of colored mixed graphs. J. Combin. Theory Ser. B, 80:147-155, 2000.

  20. P. Hell, J. Nesetril, A. Raspaud, and E. Sopena. Three and more set theorems. Comment. Math. Univ. Carolin., 41:793-801, 2000.

  21. M. Habib and C. Paul. A new vertex splitting algorithm for cograph recognition. Technical Report RR-123800, LaBRI, 2000.

  22. M. Habib, R. McConnell, C. Paul, and L. Viennot. Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science, 234:59-84, 2000.

  23. Cyril Gavoille. A survey on interval routing. Theoretical Computer Science, 245(2):217-253, 2000. Updated version of RR-1182-97 (1997).A HTML version available here.

  24. Cyril Gavoille. On the dilation of interval routing. The Computer Journal, 43(1):1-7, 2000. Updated version of RR-1145-96 (1996).

  25. Pierre Fraigniaud, Cyril Gavoille, and Bernard Mans. Interval routing schemes allow broadcasting with linear message-complexity. Research Report LRI-1241, LRI, Université Paris-Sud, 91405 Orsay cedex, France, January 2000. Extended abstract published in PODC '00, and the full version appears in JDC.

  26. G. Fertin, A. Raspaud, O. Sýkora, H. Schröder, and I. Vrto. Diameter of Knödel graph. In 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), volume 1928 of Lecture Notes in Computer Science, pages 149-160. Springer-Verlag, 2000.

  27. G. Fertin and A. Raspaud. Recognizing recursive circulant graphs G(cd^m,d). Research Report RR-1235-00, LaBRI, Université Bordeaux 1, 2000.

  28. G. Fertin and A. Raspaud. Recognizing recursive circulant graphs. In 6th International Conference on Graph Theory (ICGT 2000), volume 5 of Electronic Notes on Discrete Mathematics, 2000.

  29. G. Fertin and A. Raspaud. Gossiping in directed graphs. In 9th International Conference on Fibonacci Numbers and their Applications, 2000.

  30. G. Fertin and R. Labahn. Compounding of gossip graphs. Networks, 36(2):126-137, 2000.

  31. G. Fertin. A study of minimum gossip graphs. Discrete Mathematics, 215(1-3):33-57, 2000.

  32. G. Fertin. On the structure of minimum broadcast digraphs. Theoretical Computer Science, 245(2):203-216, 2000.

  33. G. Fertin. Hierarchical broadcast and gossip networks. Information Processing Letters, 73(3-4):131-136, 2000.

  34. D. Corneil, F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. Discrete Applied Mathematics, 2000. To appear.

  35. Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Recognizing Knödel and Fibonacci graphs. Research Report LRI-1238, LRI, Université Paris-Sud, 91405 Orsay cedex, France, January 2000. An updated version appears in Discrete Mathematics. Extended abstract published in WG '99.

  36. O.V. Borodin, A.V. Kostochka, A. Raspaud, and E. Sopena. Acyclic k-strong hypergraph coloring of maps on surfaces. Mathematical Note, 67, No. 1:29-35, 2000.

  37. O.V. Borodin, A.V. Kostochka, A. Raspaud, and E. Sopena. Acyclic coloring of 1-planar graphs (russian). Diskretn. Anal. Issled. Oper. Ser.1, 6:20-35, 2000.



1999

  1. Cyril Gavoille and David Peleg. The compactness of interval routing. SIAM Journal on Discrete Mathematics, 12(4):459-473, October 1999. Updated version of RR-1176-97 (1997).

  2. Jean-Claude Bermond, Cyril Gavoille, and André Raspaud. Proceedings of the 6th International Colloquium on Structural Information & Communication Complexity, SIROCCO 6. Carleton Scientific, July 1999.

  3. Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, 26th International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of Lecture Notes in Computer Science, pages 351-360. Springer, July 1999. Extended abstract of RR-1213-99 (1999), and a revised version is available here.

  4. Cyril Gavoille, Jean-Claude Bermond, and André Raspaud. Proceedings of the 6th International Colloquium on Structural Information & Communication Complexity, SIROCCO 6. Carleton Scientific, July 1999. Abstract and Table of Contents available here.

  5. Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Recognizing bipartite incident-graphs of circulant digraphs. In Peter Widmayer, Gabriele Neyer, and Stephan Eidenbenz, editors, 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 1665 of Lecture Notes in Computer Science, pages 215-227. Springer, June 1999. An updated version appears in Discrete Mathematics. Appears also as RR-LRI-1238 (2000).

  6. Cyril Gavoille and Nicolas Hanusse. Routage compact dans les réseaux de genre borné. In 1ère Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pages 1-5. INRIA, May 1999. Apparaît aussi dans RR-1213-99 (1999).

  7. Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. Research Report RR-1213-99, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, February 1999. Extended abstract published in ICALP '99, and a revised version is available here.

  8. P. Boiron, E. Sopena, and L. Vignal. Acyclic improper colourings of graphs. J. Graph Theory, 32:97-107, 1999. (Compressed postcript).

  9. O. Baudon, G. Fertin, and I. Havel. Routing permutations in the hypercube. In 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '99), volume 1665 of Lecture Notes in Computer Science, pages 179-190. Springer-Verlag, 1999.

  10. O. Baudon, G. Fertin, and I. Havel. Routing permutations in the hypercube. In 25th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'99, volume 1665 of Lecture Notes in Computer Science, pages 179-190. Springer-Verlag, 1999.

  11. O. Togni. All-to-all communication in all-optical circulant networks. Submitted, 1999.

  12. J. Nesetril and A. Raspaud. Duality, nowhere-zero flows, coloring and cycle covers. Texte écrit pour l'Ecole de Printemps en Combinatoire (Borová Lada). KAM-DIMATIA Series (Prague), 99-442, 1999.

  13. J. Nesetril and A. Raspaud. Antisymmetric flows and strong colourings of oriented graphs. Annales de l'Institut Fourier, 49:1037-1056, 1999.

  14. J. Nesetril and E. Sopena. On four coloring problems. Technical report, LaBRI, Université Bordeaux 1, 1999. (Compressed postcript).

  15. I. Litovsky, Y.Métivier, and E. Sopena. Graph relabelling systems and distributed algorithms. In H. Ehrig, H.-J. Kreowski, U. Montanari, and G. Rozenberg, editors, Handbook of graph grammars and computing by graph transformation, volume 3, pages 1-56. World Scientific, 1999. (Compressed postcript).

  16. D. Amar, A. Raspaud, and O. Togni. All-to-all wavelength-routing in all-optical compound networks. In Proceedings of the Fifth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. Elsevier, 1999. To be published in Discrete Math.

  17. D. Amar, A. Raspaud, and O. Togni. All-to-all wavelength-routing in all-optical compound networks. In Proceedings of the 5-Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague July 6-11, 1998. Elsevier, 1999. To appear in Discrete Math.

  18. M. Habib, C. Paul, and L. Viennot. Partition refinement: an interested algorithmic tool kit. International Journal of Foundation of Computer Science, 10(2):147-170, 1999.

  19. M. Habib, C. Paul, and L. Viennot. Linear time recognition of p_4-indifference graphs. Technical Report 3779, INRIA, 1999. To appear in DMTCS.

  20. G. Fertin and A. Raspaud. Minimum gossip digraphs. Research Report RR-1223-99, LaBRI, Université Bordeaux 1, 1999.

  21. G. Fertin. Trade-offs for odd gossiping. Research Report RR-1216-99, LaBRI, Université Bordeaux 1, 1999. Submitted for publication.

  22. G. Fertin. Trade-offs for odd gossiping. In 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO '99), volume 6 of Proceedings in Informatics, pages 137-151. Carleton Scientific, 1999.

  23. G. Fertin. Étude des communications dans les réseaux d'interconnexion. PhD thesis, Université Bordeaux I, 1999.

  24. G. Fertin. Compromis pour l'échange total impair. In 1ères Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel '99), pages 47-52. INRIA, 1999.

  25. G. Damiand, M. Habib, and C. Paul. A simple paradigm for graph recognition: application to cographs and distance hereditary graphs. Theoretical Computer Science, 1999. To appear.

  26. O.V. Borodin, A.V. Kostochka, A. Raspaud, and E. Sopena. Acyclic colouring of 1-planar graphs. Discrete Analysis and Operations Research, 6(4):20-35, 1999. (Compressed postcript).

  27. O.V. Borodin, A.V. Kostochka, J. Neset ril, A. Raspaud, and E. Sopena. On the maximal average degree and the oriented chromatic number of a graph. Discrete Math., 206:77-89, 1999.

  28. O.V. Borodin, A.V. Kostochka, J. Nesetril, A. Raspaud, and E. Sopena. On the maximum average degree and the oriented chromatic number of a graph. Discrete Math., 206:77-89, 1999. (Compressed postcript).



1998

  1. Jean-Claude Bermond, Éric Darrot, Olivier Delmas, and Stéphane Perennes. Hamilton cycle decomposition of the Butterfly network. Parallel Processing Letters, 8(3):371-385, September 1998.

  2. Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. In Shay Kutten, editor, 12th International Symposium on Distributed Computing (DISC), volume 1499 of Lecture Notes in Computer Science, pages 161-174. Springer, September 1998. An updated version appears in SIAM J. on Computing. Appears also as RR-1202-98 (1998).

  3. Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. In 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20. ACM Press, August 1998. An updated version appears in Journal of Algorithms. Appears also as RR-1195-98 (1998). Slides available here.

  4. Pierre Fraigniaud and Cyril Gavoille. A theoretical model for routing complexity. In Luisa Gargano and David Peleg, editors, 5th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 98-113. Carleton Scientific, July 1998.

  5. Olivier Delmas. Trade-off for broadcast protocols. In Luisa Gargano and David Peleg, editors, Proceedings of 5th International Colloquium on Structural Information and Communication Complexity (SIROCCO 5), Proceedings in informatics 3, pages 36-50. Carleton Scientific, June 1998.

  6. Jean-Claude Bermond, Éric Darrot, Olivier Delmas, and Stéphane Perennes. Hamilton circuits in the directed Butterfly network. Discrete Applied Mathematics, 84(1-3):21-42, May 1998.

  7. Cyril Gavoille and David Peleg. The compactness of interval routing for almost all graphs. Research Report RR-1202-98, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, April 1998. Extended abstract published in DISC '98, and a revised version appears in SIAM J. on Computing.

  8. O. Togni. Optical all-to-all communication in inflated networks. In Proc. of the 5th annual International Workshop on Graph-Theoretic Concepts in Computer Science, WG'98, Lecture Notes in Computer Science. Springer Verlag, 1998.

  9. C. Paul. Parcours en largeur lexicographique : un algorithme de partitionnement, application aux graphes et généralisation. PhD thesis, LIRMM, Université de Montpellier II, 1998.

  10. D. Amar and O. Togni. Irregularity strength of trees. Discrete Math., 190(1-3):15-38, 1998.

  11. D. Amar and O. Togni. Irregularity strengh of trees. Discrete Math., 190:15-38, 1998.

  12. M. Habib, C. Paul, and L. Viennot. A synthesis on partition refinement: a useful routine for strings, graphs, boolean matrices and automata. In STACS 98, number 1373 in LNCS, pages 25-38. 15th Symposium on Theoretical Aspect of Computer Science, 1998.

  13. Cyril Gavoille and Eric Guévremont. Worst case bounds for shortest path interval routing. Journal of Algorithms, 27(1):1-25, 1998. Updated version of RR95-02 (1995).

  14. G. Gauyacq, C. Micheneau, and A.Raspaud. Routing in recursive circulant graphs : edge-forwarding index and hamiltonian decomposition. In Juraj Hromkovic and Ondrej Sijkora, editors, Graph-Theoretic Concepts in Computer Science, WG'98, Lecture Notes in Computer Science, pages 227-241, 1998.

  15. Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Algorithmica, 21:155-182, 1998. Updated version of RR94-04 (1994).

  16. D. Amar, S. Brandt, D. Brito, and O. Ordaz. Neighborhood conditions for independent sets in bipartite graphs. Discrete Math., 181:31-36, 1998.

  17. G. Fertin and A. Raspaud. Families of graphs having broadcasting and gossiping properties. In 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '98), volume 1517 of Lecture Notes in Computer Science, pages 63-77. Springer-Verlag, 1998.

  18. G. Fertin and J.G. Peters. Optimal odd gossiping. Research Report CMPT TR 1998-24, Simon Fraser University, Burnaby, B.C., 1998. Submitted for publication.

  19. G. Fertin and J.G. Peters. Odd gossiping in the linear cost model. In Workshop on Communication - 23rd Int. Symp. on Mathematical Foundations of Computer Science (MFCS '98), 1998.

  20. Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. Research Report RR-1195-98, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, January 1998. A part appears in Journal of Algorithms (and an extended abstract has been published in PODC '98), and another part appears here.

  21. D. Corneil, F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. In Graph-Theoretic Concepts in Computer Science, WG'98, volume 1517 of Lecture Notes in Computer Science. 24st Internationnal Workshop WG'98, 1998.

  22. J. Cohen, P. Fraigniaud, J.-C. Konig, and A. Raspaud. Optimized broadcasting and multicasting protocols in cut-through routed networks. IEEE Transactions on Parallel and Distributed Systems, 9:788-802, 1998.

  23. O.V. Borodin, A.V. Kostochka, J. Neset ril, A. Raspaud, and E. Sopena. On universal graphs for planar oriented graphs of a given girth. Discrete Math., 188:73-85, 1998.

  24. O.V. Borodin, A.V. Kostochka, J. Nesetril, A. Raspaud, and E. Sopena. On universal graphs for planar oriented graphs of a given girth. Discrete Math., 188:73-85, 1998. (Compressed postcript).

  25. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In 19th International Symposium on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science, pages 442-456. Springer, September 2005. Slides available here.



1997

  1. Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Research Report RR-1181-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1997. Extended abstract published in SIROCCO '97. Appears also in JPDC.

  2. Cyril Gavoille. A survey on interval routing scheme. Research Report RR-1182-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1997. An updated version appears in TCS, and a HTML version available here.

  3. Cyril Gavoille and David Peleg. The compactness of interval routing. Research Report RR-1176-97, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, September 1997. An updated version appears in SIAM Journal on Discrete Mathematics.

  4. Cyril Gavoille. On the dilation of interval routing. In Igor Prívara and Peter Ruzicka, editors, 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 1300 of Lecture Notes in Computer Science, pages 259-268. Springer, August 1997. Appears also as RR-1145-96 (1996).

  5. Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. In Danny Krizanc and Peter Widmayer, editors, 4th International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 162-175. Carleton Scientific, July 1997. Appears also as RR-1181-97 (1997).

  6. Cyril Gavoille. Compact routing: Lower bounds techniques (invited lecture). In International Research School on "Sense of Direction and Compact Routing", June 1997.

  7. P. Boiron, E. Sopena, and L. Vignal. Acyclic improper colourings of graphs with bounded degree. In Proc. DIMACS/DIMATIA Conf. Contemporary trends in Discrete Math., Dimacs Series in Discrete Math. and Theoret. Comput.Sci., volume 49, pages 1-10, 1997. (Compressed postcript).

  8. O. Togni. Irregularity strength of the toroidal grid. In 5ième Colloque International de Théorie des Graphes et Combinatoire, Luminy, volume 165-166 of Discrete Math., pages 609-620. Elsevier, 1997.

  9. E. Sopena. The chromatic number of oriented graphs. J. Graph Theory, 25:191-205, 1997. (Compressed postcript).

  10. J. Nesetril, A. Raspaud, and E. Sopena. Colorings and girth of oriented planar graphs. Discrete Math., 165-166:519-530, 1997.

  11. J. Nesetril, E. Sopena, and L. Vignal. T-preserving homomorphisms of oriented graphs. Comment. Math. Univ. Carolinae, 38-1:125-136, 1997. (Compressed postcript).

  12. J. Nesetril, A. Raspaud, and E. Sopena. Colorings and girth of oriented planar graphs. Discrete Math., 165-166:519-530, 1997. (Compressed postcript).

  13. Y. Métivier and E. Sopena. Graph relabelling systems: a general overview. Computers and Artificial Intelligence, 16(2):167-185, 1997. (Compressed postcript).

  14. R. Labahn and A. Raspaud. Periodic gossiping in back-to-back trees. Discrete Applied Math., 75:157-168, 1997.

  15. A.V. Kostochka, E. Sopena, and X. Zhu. Acyclic and oriented chromatic numbers. J. Graph Theory, 24(4):331-340, 1997. (Compressed postcript).

  16. A. V. Kostochka, T. Luczak, G. Simonyi, and E. Sopena. On the minimum number of edges giving maximum oriented chromatic number. In Proc. DIMACS/DIMATIA Conf. Contemporary trends in Discrete Math., Dimacs Series in Discrete Math. and Theoret. Comput. Sci., volume 49, pages 179-182, 1997. (Compressed postcript).

  17. M. Habib, R. McConnell, C. Paul, and L. Viennot. Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science, 1997. To appear.

  18. G. Gauyacq. On quasi-cayley graphs. Discrete Applied Math., 77:43-58, 1997.

  19. G. Gauyacq. Edge-forwarding index of star graphs and other cayley graphs. Discrete Applied Math., 80:149-160, 1997.

  20. Pierre Fraigniaud and Cyril Gavoille. Universal routing schemes. Distributed Computing, 10:65-78, 1997. Updated version of RR95-05 (1995).

  21. Olivier Delmas and Stéphane Perennes. Diffusion par commutation de circuits dans les tores de dimension k / Circuit-switched broadcasting in the k-dimensional torus networks. Technique et science informatiques, 16(5):563-581, 1997. RAIRO, afcet, Hermès.

  22. Olivier Delmas. Communications par commutation de circuits dans les réseaux d'interconnexion. Thèse de doctorat, Université de Nice - Sophia Antipolis, U.F.R. de Sciences, École doctorale sciences pour l'ingénieur, France, January 1997.



1996

  1. Cyril Gavoille. On dilation of interval routing. Research Report RR-1145-96, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, November 1996. An updated version appears in The Computer Journal and in MFCS '97.

  2. Cyril Gavoille. Lower bounds for interval routing on bounded degree networks. Research Report RR-1144-96, LaBRI, University of Bordeaux 1, 351, cours de la Libération, 33405 Talence Cedex, France, October 1996. Submitted for publication.

  3. Olivier Delmas and Stéphane Perennes. Circuit-Switched Gossiping in 3-Dimensional Torus Networks. In L. Bougé, P. Fraigniaud, A. Mignotte, and Y. Robert, editors, Proceedings of the Euro-Par'96 Parallel Processing / Second International EURO-PAR Conference, volume 1123 of Lecture Notes in Computer Science, pages 370-373, Lyon, France, August 1996. Springer Verlag. (Version étendue disponible en rapport de recherche 2930 de l'Unité de recherche INRIA Sophia Antipolis - Juillet 1996, France.), Research Report 2930, INRIA.

  4. Cyril Gavoille and Stéphane Pérennès. Lower bounds for interval routing on 3-regular networks. In Nicola Santoro and Paul Spirakis, editors, 3rd International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 88-103. Carleton University Press, June 1996.

  5. Pierre Fraigniaud and Cyril Gavoille. Local memory requirement of universal routing schemes. In 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 183-188. ACM Press, June 1996. Appears also as RR96-01 (1996). Appears also in Journal of Distributed Computing (1997).

  6. Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. In 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125-133. ACM Press, May 1996. BEST STUDENT PAPER AWARD. Appears also as RR95-46 (1995) and I3S 95-37 (1995).

  7. Olivier Delmas and Stéphane Perennes. Diffusion en mode commutation de circuits. In R. Castanet and J. Roman, editors, Proceedings of the 8th RenPar Conference, pages 53-56, Bordeaux, France, May 1996.

  8. Cyril Gavoille and Stéphane Pérennès. Lower bounds for shortest path interval routing. Research Report 96-08, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, April 1996.

  9. O. Baudon and J.-M. Laborde. Cabri-graph, a sketchpad for graph theory. Mathematics and Computers in Simulation, 1340:1-10, 1996.

  10. E. Sopena and L. Vignal. A note on the chromatic number of graphs with maximum degree three. Technical Report 1125-96, LaBRI, Université Bordeaux 1, 1996. (Compressed postcript).

  11. E. Sopena. Expanding graph relabeling systems have the power of recursive enumerability. Fundamentae Informatica, 27(1):1-26, 1996. (Compressed postcript).

  12. C. Micheneau. Griap : a new way to develop communication schemes in interconnection networks. In Proceedings de Parco 95, 1996. A paraître.

  13. C. Micheneau. Graphes récursifs circulants, communications vagabondes et simulation. Thèse de doctorat, Université Bordeaux I, 1996.

  14. I. Litovsky, Y.Métivier, and E. Sopena. Checking global graph properties by means of local computations: the majority problem. Electronic Notes in Comput. Sci., 2, 1996. (Compressed postcript).

  15. D. Amar, O. Ordaz, and A. Raspaud. Hamiltonian properties and the bipartite independence number. Discrete Math., 161:207-215, 1996.

  16. Cyril Gavoille. Complexité mémoire du routage dans les réseaux distribués. PhD thesis, École Normale Supérieure de Lyon, 46, allée d'Italie, January 1996. The cover page is available here.

  17. Pierre Fraigniaud and Cyril Gavoille. Local memory requirement of universal routing schemes. Research Report 96-01, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1996. Extended abstract published in SPAA '96.



1995

  1. Cyril Gavoille and Stéphane Pérennès. Memory requirement for routing in distributed networks. Research Report 95-46, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, December 1995. Extended abstract published in PODC '96.

  2. P. Galinier, M. Habib, and C. Paul. Maximal intersection search: a new algorithm for chordal graph recognition. Technical Report 95044, LIRM Montpellier, October 1995.

  3. Cyril Gavoille and Stéphane Pérennès. Routing memory requirement for distributed networks. Research Report 95-37, I3S, Université de Nice-Sophia Antipolis, 06903 Sophia Antipolis, France, August 1995. Extended abstract published in PODC '96.

  4. Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. In 14th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 223-230. ACM Press, August 1995. An updated version is available in the Journal of Distributed Computing.

  5. Cyril Gavoille and Eric Guévremont. On the compactness of bounded degree graphs for shortest path interval routing. In 2nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), pages 113-121. Carleton University Press, June 1995.

  6. P. Galinier, M. Habib, and C. Paul. Chordal graphs and their clique graph. In M. Nagl (Ed.), editor, Graph-Theoretic Concepts in Computer Science, WG'95, volume 1017 of Lecture Notes in Computer Science, pages 358-371, Aachen, Germany, June 1995. 21st Internationnal Workshop WG'95, Springer.

  7. Pierre Fraigniaud and Cyril Gavoille. Memory requirement for universal routing schemes. Research Report 95-05, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, March 1995. An updated version is available in the Journal of Distributed Computing.

  8. A. Bel Hala. Communications dans les réseaux d'interconnexion : plongements optimaux de l'hypercube. Thèse de doctorat, Université Bordeaux I, 1995.

  9. D. Barth, F. Pellegrini, A. Raspaud, and J. Roman. On bandwidth, cutwidth and quotient graphs. RAIRO, 29:487-508, 1995.

  10. D. Barth, J. Bond, and A. Raspaud. Compatible eulerian circuits in k**. Discrete Applied Math, 56:127-136, 1995.

  11. A. Raspaud, O. Sýkora, and I. Vrt'o. Cutwidth of the de bruijn graph. RAIRO, 29:509-514, 1995.

  12. C. Micheneau. Griap : a new way to develop communication schemes in interconnection networks. Rapport Interne 1097-95, LaBRI, Université Bordeaux I, 1995.

  13. C. Micheneau. Disjoint hamiltonian cycles in recursive circulant graphs. Rapport Interne 1080-95, LaBRI, Université Bordeaux I, 1995. A paraître dans I.P.L.

  14. I. Litovsky, Y.Métivier, and E. Sopena. Different local controls for graph relabeling systems. Math. Systems Theory, 28:41-65, 1995. (Compressed postcript).

  15. Cyril Gavoille and Eric Guévremont. Worst case bounds for shortest path interval routing. Research Report 95-02, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1995. An updated version appears in Journal of Algorithms.

  16. D. Amar, O. Favaron, P. Mago, and O. Ordaz. Biclosure and bistability in a balanced bipartite graph. Journal of Graph Theory, 20:513-529, 1995.

  17. G. Gauyacq. Routages uniformes dans les graphes sommet-transitifs. Thèse de doctorat, Université Bordeaux I, 1995.

  18. D. Amar, S. Brandt, D. Brito, and O. Ordaz. Neighborhood conditions for balanced independent sets in bipartite graphs. Rapport interne, Freie Universität Berlin, 1995.

  19. G. Fertin. Etude des graphes minimaux pour l'échange total. Master's thesis, DEA Informatique, Université Bordeaux 1, 1995.

  20. V. Albiero and E. Sopena. Combinatorial construction of time-stamp systems. In Proc. Formal Power Series and Algebraic Combinatorics, FPSAC'95, 1995. (Compressed postcript).



1994

  1. Pierre Fraigniaud and Cyril Gavoille. Optimal interval routing. In Bruno Buchberger and Jens Volkert, editors, Parallel Processing: CONPAR '94 - VAPP VI, volume 854 of Lecture Notes in Computer Science, pages 785-796. Springer-Verlag, September 1994.

  2. Pierre Fraigniaud and Cyril Gavoille. A characterization of networks supporting linear interval routing. In 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 216-224. ACM Press, August 1994.

  3. Cyril Gavoille. Routages efficaces et compacts. In Luc Bougé, Michel Cosnard, and Pierre Fraigniaud, editors, 6èmes Rencontres Francophones du Parallélisme (RenPar), page 298, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, June 1994.

  4. D. Barth and A. Raspaud. Two disjoint hamiltonian cycles in the butterfly graph. Information Processing Letters, 51:175-179, 1994.

  5. D. Barth, A. Bel Hala, and C. Micheneau. Griap : un logiciel d'aide à la mise au point d'algorithmes de communication dans les réseaux d'interconnexion. In RENPAR'6, pages 213-216, 1994.

  6. D. Barth. Réseaux d'interconnexion : structures et communications. Thèse de doctorat, Université Bordeaux I, 1994.

  7. D. Barth. Embedding by exclusions. In DIMACS Workshop Proposal : Interconnection Networks and Mapping and Scheduling Parallel Computations, Rutgers University, 1994.

  8. A. Raspaud and E. Sopena. Good and semi-strong colorings of oriented planar graphs. Information Processing Letters, 51:171-174, 1994.

  9. Pierre Fraigniaud and Cyril Gavoille. Interval routing schemes. Research Report 94-04, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, January 1994. An updated version appears in Algorithmica.

  10. G. Fan and A.Raspaud. Fulkerson's conjecture and circuit covers. J. Combin. Theory Ser. B, 61:133-138, 1994.

  11. J. de Rumeur. Communication dans les réseaux de processeurs. Masson, 1994.



1993

  1. O. Baudon. Le projet GSK. Orsay, Novembre 1993. Journées GDR-Programmation.

  2. Frédéric Desprez, Cyril Gavoille, Bruno Jargot, and Makan Pourzandi. Tests des performances des communications de la machine Volvox IS-860. La lettre du Transputer et des Calculateurs Parallèles, 19:11-35, October 1993. Updated version of TR93-02 (1993).

  3. Cyril Gavoille. Routage par intervalles. Stage de DEA, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, June 1993.

  4. Frédéric Desprez, Cyril Gavoille, Bruno Jargot, and Makan Pourzandi. Tests des performances des communications de la machine Volvox IS-860. Technical Report 93-02, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, March 1993. Appears also as La Lettre du Transputeur.

  5. A. Bel Hala. Congestion optimale du plongement de l'hypercube h(n_1+n_2+...+n_d) dans la grille à d dimensions gr(2n_1, 2n_2,...,2n_d). Rapport Interne 93-21, LaBRI, Université Bordeaux I, 1993. Soumis pour publication.

  6. A. Bel Hala. Congestion optimale du plongement de l'hypercube h(n) dans la chaîne p(2n). Informatique théorique et Applications, 5:465-481, 1993.

  7. O. Baudon and J.-M. Laborde. Cabri-graph, a sketchpad for graph theory. In G. Jacob, N.E. Oussous, and S. Steinberg, editors, IMACS Symposium on Symbolic Computation, New Trends and Developments, pages 50-55, 1993.

  8. D. Barth. Embedding meshes of d-ary trees into de Bruijn graphs. Parallel Processing Letters, 3(2):115-127, 1993.

  9. A. Raspaud. Postman tours and cycle covers. Discrete Math., 111:447-454, 1993.

  10. A. Raspaud. Good and semi-strong colorings of oriented planar graphs. Bulletin of the EATCS, 50:260-263, 1993.

  11. D. Amar, D. Brito, and O. Ordaz. Hamiltonism and neighborhood of balanced bipartite sets in bipartite graphs. Rapport interne, LaBRI, Université Bordeaux I, 1993. Soumis pour publication.

  12. D. Amar, D. Brito, and O. Ordaz. Hamiltonian cycles and hamiltonian-biconnectedness in bipartite digraphs. Rapport interne, LaBRI, Université Bordeaux I, 1993. Soumis pour publication.

  13. D. Amar, D. Brito, and O. Ordaz. Balanced bipartite sets and cycles in bipartite graphs. Rapport interne, LaBRI, Université Bordeaux I, 1993. Soumis pour publication.

  14. D. Amar. Irregularity strength of regular graphs of large degree. Discrete Math., 114:9-17, 1993.

  15. D. Amar. Applying a condition for a hamiltonian bipartite graph to be bipancyclic. Discrete Math., 111:19-25, 1993.



1992

  1. Cyril Gavoille. Evaluation of the MasPar MP-1 performances. Technical Report 92-01, LIP, École Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France, February 1992.

  2. A. Raspaud. Short circuit covers for binary matroids with a Petersen flow. Technical Report 92-03, LaBRI, Université Bordeaux I, 1992.

  3. A. Raspaud. Cycle covers of graphs with the Fulkerson property. In VI Jordanas en teoria de grafos y sus aplicaciones. Cumaná (Venezuela), 1992.

  4. A. Raspaud. Cycle covers and nowhere-zero flows. In VI Jordanas en teoria de grafos y sus aplicaciones. Cumaná (Venezuela), 1992.

  5. D. Amar and Y. Manoussakis. Hamiltonian paths and cycles, number of arcs and independance number in digraphs. Discrete Math., 105:1-16, 1992.

  6. D. Amar. Paths and cycles in bipartite graphs. In VI Jordanas en teoria de grafos y sus aplicaciones. Cumaná (Venezuela), 1992.

  7. D. Amar. Hamiltonism in bipartite digraphs. In VI Jordanas en teoria de grafos y sus aplicaciones. Cumaná (Venezuela), 1992.

  8. D. Amar. A condition for a hamiltonian bipartite graph to be bipancyclic. Discrete Math., 102:221-227, 1992.



1991

  1. A. Raspaud. Cycle covers of graphs with a nowhere-zero 4-flow. Journal of Graph Theory, 15(6):649-654, 1991.

  2. D. Amar and A. Raspaud. Covering the vertices of a digraph by cycles of prescribed length. Discrete Math., 87:111-118, 1991.



1990

  1. O. Baudon. Cabri-graphes, un cahier de brouillon interactif pour la théorie des graphes. PhD thesis, Université Joseph Fourier-Grenoble 1, 1990.



1987

  1. U. Jamshy, A. Raspaud, and M. Tarsi. Short circuit covers for regular matroids with a nowhere zero 5-flow. J. Combin. Theory Ser. B.43, 3:354-357, 1987.



10 janvier 2008 (456)
[home page of the team]