Pierre Fraigniaud's Publications

2005

• A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs P. Fraigniaud. Technical Report LRI-1397, University Paris-Sud, Feb. 2005.

2004

• Eclecticism Shrinks Even Small Worlds P. Fraigniaud, C. Gavoille, and C. Paul. To appear in 23rd ACM Symp. on Principles of Distributed Computing (PODC 2004).
• Digraphs Exploration with Little Memory P. Fraigniaud and D. Ilcinkas. In 21st Symposium on Theoretical Aspects of Computer Science (STACS), Montpellier, March 25-27, 2004
• Graph Exploration by a Finite Automaton P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg. To appear in 29th Symposium on Mathematical Foundations of Computer Science (MFCS), 2004.
• Collective Tree Exploration P. Fraigniaud, L. Gasieniec, D. Kowalski, and A. Pelc. In 6th Latin American Theoretical Informatics Symposium (LATIN), Buenos Aires, April 2004
• Reducing Packet-Loss by Taking Long-Range Dependences into Account J. I. Alvarez-Hamelin and P. Fraigniaud. In 3rd IFIP Networking Conference (Networking 2004), Athens, May 9-14, 2004.

2003

• Eclecticism Shrinks the World .ps .pdf P. Fraigniaud, C. Gavoille and C. Paul. Technical Report LRI-1376, University Paris-Sud, Nov. 2003.
• Tree Exploration with Little Memory
  K. Diks, P. Fraigniaud, E. Kranakis and A. Pelc. To appear in Journal of Algorithms.
• Deterministic rendezvous in graphs A. Dessmark, P. Fraigniaud and A. Pelc. In 11th Annual European Symposium on Algorithms (ESA), Budapest, Sept 2003.
• An Overview of the Content-Addressable Network D2B. P. Fraigniaud and P. Gauron. Brief Announcement at 22nd ACM Symp. on Principles of Distributed Computing (PODC), July 2003. Full version: Tech. Rep. 1349 LRI, Univ. Paris-Sud, France. January 2003.
• Lowers Bounds for Oblivious Single-Message End-to-End Communication. P. Fraigniaud and Cyril Gavoille. In 17th Symposium on Distributed Computing (DISC), October 2003.
• A Multicast Protocol with QoS Support I. Alvarez-Hamelin and P. Fraigniaud. In 12th Int. Conference on Computer Communications and Networks (ICCCN), Oct. 2003.
• Searching is not Jumping L. Barrière, P. Fraigniaud, N. Santoro, and D. Thilikos. In 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003). Full version as Technical report, Dep. de Llenguatges i Sistemes Informàtics, UPC, Barcelona, Spain, 2002.
• Can we elect if we cannot compare? L. Barrière, P. Flocchini, P. Fraigniaud and N. Santoro. To appear in 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2003.
• Dynamic construction of Bluetooth scatternets of fixed degree and low diameter. L. Barrière, P. Fraigniaud, L. Narayanan, and J. Opatrny. In 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp781-790, January 2003.

2002

• Robust Position-Based Routing in Wireless Ad Hoc Networks with Irregular Transmission Ranges
  Lali Barrière, Pierre Fraigniaud, Lata Narayanan, and Jaroslav Opatrny. To appear in Wireless Communications And Mobile Computing journal.
• Polynomial Time Algorithms for Minimum-Time Broadcast in Tree
  J. Cohen, P. Fraigniaud and M. Mitjana. Theory of Computing Systems 35(6), pp641 - 665, 2002.
• Capture of an Intruder by Mobile Agents
  L. Barrière, P. Flocchini, P. Fraigniaud and N. Santoro. In 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 200-209, 2002.
• A Space Lower Bound for Routing in Trees
  P. Fraigniaud and C. Gavoille. In 19th Int. Symposium on Theoretical Aspects of Computer Science (STACS), vol 2285 of LNCS, pages 65-75. Springer, 2002.
• Tree Exploration with Little Memory
  K. Diks, P. Fraigniaud, E. Kranakis and A. Pelc. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), pages 588-597, 2002. (Full version: Tech. Report LRI-1303)
• Oriented hypercubes
  P. Fraigniaud, J.-C. Konig and E. Lazard. Networks, 39(2):98-106, 2002.
• Distributed Mobile Computing with Incomparable Labels.
  L. Barrière, P. Flocchini, P. Fraigniaud and N. Santoro. Technical Report LRI-1309, Univ. Paris-Sud, France, 2002.
• Electing a leader among anonymous mobile agents in anonymous networks with sense-of-direction.
  L. Barrière, P. Flocchini, P. Fraigniaud and N. Santoro. Technical Report LRI-1310, Univ. Paris-Sud, France, 2002.

2001

• Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode
  Pierre Fraigniaud. In 9th Annual European Symposium on Algorithms (ESA '01), LNCS Vol. 2161, pages 440-451, 2001.
• Routing in Trees
  Pierre Fraigniaud and Cyril Gavoille. In 28th International Colloquium on Automata, Languages and Programming (ICALP '01), LNCS 2076, pages 757-772, Jul. 2001.
• Robust Position-Based Routing in Wireless Ad Hoc Networks with Irregular Transmission Ranges
  Lali Barrière, Pierre Fraigniaud, Lata Narayanan, and Jaroslav Opatrny. In 5th ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM '01), Rome, Italy, July 21, 2001.
• Efficient Routing in Networks with Long Range Contacts
  Lali Barrière, Pierre Fraigniaud, Evangelos Kranakis and Danny Krizanc. In 15th International Symposium on Distributed Computing (DISC '01), pages 270-284, LNCS 2180, Spinger, 2001.
• Minimum-Time Broadcast under Edge-Disjoint Paths Modes
  Pierre Fraigniaud. In 2nd International Conference on Fun with Algorithms (FUN '01), Carleton Scientific, pages 133-148, 2001.
• Assigning labels in unknown anonymous networks with a leader
  Pierre Fraigniaud, Andrzej Pelc, David Peleg and Stephane Perennes. Distributed Computing, Vol. 14, No. 3, pages 163-183, 2001
• HiHCoHP-Toward a Realistic Communication Model for Hierarchical HyperClusters of Heterogeneous Processors
  F. Cappello, P. Fraigniaud, B. Mans and A.L. Rosenberg, In 15th Annual International Parallel and Distributed Processing Symposium (IPDPS 2001).
• Minimum Linear Gossip Graphs and Maximal Linear (Delta,k)-Gossip Graphs
  P. Fraigniaud and J. Peters. Networks 38, pages 150-162, 2001
  
• Recognizing Knodel graphs
  Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. Discrete Mathematics, 250 (2002) 41-62.
• Multicast Tree with Minimum Congestion
  J. Ignacio Alvarez-Hamelin and Pierre Fraigniaud. To appear in the 3rd Rencontres Francophones sur les aspects Algorithmiques des Telecommunications (AlgoTel '01), Saint Jean de Luz, France, May 28-30, 2001.
  

2000

• Approximation Algorithms for Collective Communications with Limited Link and Node-Contention
  Pierre Fraigniaud. Technical Report LRI-1264, Universite Paris-Sud, France.
• Broadcasting and Multicasting in Trees
  Johanne Cohen and Pierre Fraigniaud. Technical Report LRI-1265, Universite Paris-Sud, France.
• Interval Routing Schemes allow Broadcasting with Linear Message-Complexity
  Pierre Fraigniaud, Cyril Gavoille and Bernard Mans. 19th ACM Symposium on Principles of Distributed Computing (PODC 2000).
• Recognizing Abelian Cayley Colored Digraphs
  Lali Barrière, Pierre Fraigniaud, Cyril Gavoille and Bernard Mans. 8th Annual European Symposium on Algorithms (ESA 2000)
• Assigning labels in unknown anonymous networks
  Pierre Fraigniaud, Andrzej Pelc, David Peleg and Stéphane Pérennes. 19th ACM Symposium on Principles of Distributed Com puting (PODC 2000).
• Scheduling Jobs in O(congestion+dilation) with Applications to Multi-point Communication Problems
  Dominique Barth and Pierre Fraigniaud. Technical Report LRI-1239, Univ. Paris-Sud, Orsay, France. (Extended version of SPAA '97.)
• Oriented hypercubes
  Pierre Fraigniaud, Jean-Claude Konig and Emmanuel Lazard. Technical Report LRI-1254, Univ. Paris-Sud, Orsay, France. May 2000.

1999

• Scheduling calls for multicasting in tree-networks
  J. Cohen, P. Fraigniaud and M. Midjana. Short paper at the 10th ACM-SIAM Symp. on Discrete Algorithms (SODA '99), 1999.
• Recognizing Bipartite Incident-Graphs of Circulant Digraphs
  Johanne Cohen, Pierre Fraigniaud, and Cyril Gavoille. 25-th Workshop on Graph-Theoretic Concepts in Computer Science (WG '99), LNCS 1665, pp215-227, 1999.
• Minimal Contention-free Matrices with Application to Multicasting
  J. Cohen, P. Fraigniaud and M. Midjana. DIMACS Workshop on Robust Communication Networks.
• Comparison of heuristics for one-to-all and all-to-all communications in partial meshes
  P. Fraigniaud and S. Vial. Parallel Processing Letters 9(1), pages 9-20, 1999.

1998

• Unslotted deflection routing
  T. Chich and P. Fraigniaud. IEEE GLOBECOM '98, vol.3, pp1641-1646, 1998.
• A theoretical model for routing complexity.
  Pierre Fraigniaud and Cyril Gavoille. 5th International Colloquium on Structural Information and Communication Complexity (SIROCCO '98), Carleton Scientific, 1998.
• Hierarchical Broadcast Networks
  P. Fraigniaud. Information Processing Letters 68, pp303-305, 1998.
• A general Theory for Deadlock Avoidance in Wormhole-Routed Networks
  E. Fleury and P. Fraigniaud. IEEE Transaction on Parallel and Distributed Systems, 9(7), pp626-638, 1998.
• Optimized broadcasting and multicasting protocols in cut-through routed networks
  Johanne Cohen, P. Fraigniaud, Jean-Claude Konig and André Raspaud. IEEE transaction on Parallel and Distributed Systems, 9(8), pp788-802, 1998.
+
• Strategies for multicasting in wormhole-routed meshes
  E. Fleury and P. Fraigniaud. Journal of Parallel and Distributed Computing, 53(1), pp26-62, 1998.
• A note on XRAM and PRAM models, and on data-movement-intensive problems
  P. Fraigniaud, Theoretical Computer Science, no. 194, p. 225-237, 1998
• Interval Routing Schemes P. Fraigniaud and C. Gavoille, Algorithmica, no. 21, p. 155-182, 1998
• Unslotted deflection routing: a practical and efficient protocol for multi-hop optical networks
  T. Chich and J. Cohen and P. Fraigniaud. LRI RR no. 1154, 1998. (Also in IEEE/ACM Transaction on Networking 9(1), pp.47-58, 2001.)

1997

• An extended comparison of slotted and unslotted deflection routing
  Thierry Chich and Pierre Fraigniaud, ICCCN'97, IEEE, 1997
• Approximation algorithms for broadcasting and gossiping
  P. Fraigniaud and S. Vial, Journal of Parallel and Distributed Computing, vol. 43, p. 47-55, 1997
• Approximation algorithms for structured communication problems
  Dominique Barth and Pierre Fraigniaud, 9th annual Symposium on parallel algorithms and architectures (SPAA'97), ACM, p. 180-188, 1997
• Broadcasting and Multicasting in Cut-through Routed Networks
  J. Cohen and P.Fraigniaud and J-C. Konig and A.Raspaud, International Parallel Processing Symposium (IPPS'97), IEEE, 1997
• Deadlock avoidance in wormhole-routed networks
  E. Fleury and P. Fraigniaud, 10th ISCA Int. Conference on Parallel and Distributed Computing Systems (PDCS'97), ACM Eds., p. 378-384, 1997
• Heuristics Algorithms for Personalized Communication problems in Point-to-Point Networks
  Pierre Fraigniaud and Sandrine Vial, SIROCCO'97 (4th International Colloquium on Structural Information and Communication Complexity), 1997
• Ordinateurs et calcul parallèles (Chapitre de Livre)
  F. Desprez and P. Fraigniaud, chap. Les bibliothèques de communication, OFTA, 1997
• Universal Routing Schemes
  P. Fraigniaud and C. Gavoille, Distributed Computing, vol. 10, p. 65-78, 1997

1996

• Analysis of Deadlock-Free Path-Based Wormhole Multicasting in Meshes in Case of Contention
  E. Fleury and P. Fraigniaud, 6th Symposium on the Frontiers of Massively Parallel Computing (Frontiers' 96), 1996
• Approximation Algorithms for Information Dissemination Problems
  Pierre Fraigniaud and Sandrine Vial, IEEE Second International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP-96), IEEE Singapore Section Eds., p. 155-162, jun, 1996
• Local Memory Requirement of Universal Routing Schemes
  Pierre Fraigniaud and Gavoille, Cyril, 8th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), ACM PRESS Eds., p. 183-188, jun, 1996
• Minimum gossip bus networks
  P. Fraigniaud and C. Laforest, Networks, vol. 27, p. 239-251, 1996

1995

• Antepenultimate broadcasting
  J-C. Bermond and P. Fraigniaud and Joe Peters, Networks, vol. 26, p. 125-137, 1995
• Memory Requirement for Universal Routing Schemes
  Pierre Fraigniaud and Gavoille, Cyril, 14th Annual ACM Symposium on Principles of Distributed Computing (PODC'95), ACM PRESS Eds., p. 223-230, aug, 1995
• Structured Communications in Torus Networks
  P. Fraigniaud and Joe Peters, 28th Hawaii International Conference on System Sciences, IEEE, p. 584-593, 1995

1994

• A Characterisation of Networks supporting Linear Interval Routing
  Pierre Fraigniaud and Gavoille, Cyril, 13th Annual ACM Symposium on Principles of Distributed Computing (PODC'94), ACM PRESS Eds., p. 216-224, aug, 1994
• Analysis of Asynchronous Polynomial Root Finding Methods on a Distributed Memory Multicomputer
  M. Cosnard and P. Fraigniaud, IEEE Transaction on Parallel and Distributed Systems, vol. 5, no. 6, p. 639-648, 1994
• Broadcasting and Gossiping in de Bruijn Networks
  J-C. Bermond and P. Fraigniaud , SIAM Journal on Computing, vol. 23, no. 1, p. 212-225, 1994
• Communication dans les réseaux de processeurs
  J-C. Bermond and P. Fraigniaud and A. Germa and M-C. Heydemann and E. Lazard and P. Michallon and A. Raspaud and D. Sotteau and M. Syska and D. Trystram, Masson, 1994
  
• Disjoint spanning trees of small depth
  P. Fraigniaud and C. Laforest, Parallel Computing: trends and application (ParCo'94), G. Joubert, D. Trystram, F. Peters and D.Evans Eds., Elsevier Science, p. 105-112, 1994
• Methods and Problems of Communication in Usual Networks
  P. Fraigniaud and E. Lazard, Discrete Applied Mathematics, vol. 53, p. 79-133, 1994
• Minimum linear gossip graphs and maximal Linear (Delta,k)-gossip graphs
  P. Fraigniaud and J. Peters, no. CMPT TR 94-06, 1994
  
• Open problems (Divers)
  P. Fraigniaud and A. Liestman and D. Sotteau, 1994
  Notes: (Compilation de problèmes ouverts)
• Optimal Interval Routing
  Pierre Fraigniaud and Gavoille, Cyril, Parallel Processing: CONPAR '94 - VAPP VI, Bruno Buchberger and Jens Volkert Eds., vol. 854 of Lecture Notes in Computer Science, Springer-Verlag, p. 785-796, sep, 1994
• Strategies for multicasting in meshes
  E. Fleury and P. Fraigniaud, 23-rd International Conference on Parallel Processing (ICPP'94), 1994

1993

• Finding a target subnetwork in sparse networks with random faults
  P. Fraigniaud and C. Kenyon and A. Pelc, Information Processing Letters, vol. 48, p. 297-303, 1993
• Scheduling a scattering-gathering sequence on hypercube
  H-P. Charles and P. Fraigniaud, Parallel Processing Letters, vol. 3, no. 1, p. 29-42, 1993

1992

• Asymptotically Optimal Broadcasting and Gossiping in Faulty Hypercubes Multicomputers
  P. Fraigniaud, IEEE Transaction on Computers, vol. 41, no. 11, p. 1410-1419, 1992
• Broadcasting and NP-Completeness
  J-C. Bermond and P. Fraigniaud, Graph Theory Notes of New York, Kennedy and Quintas Eds., vol. XXII, p. 8-14, 1992
• Fine and coarse grained parallel implementations of polynomial root finding algorithms
  E. Fleury and P. Fraigniaud, World Congress of Non-linear Analists (WCNA'92), Tempa, 1992
• Influence of the SIMD programming mode on sorting and extracting the roots of a polynomial
  P. Fraigniaud and M. Gastaldo, Parallel and Distributed Computing and Systems, R. Melhem Eds., ISMM, p. 230--237, 1992
• Performance analysis of broadcasting in hypercubes with restricted communication capabilities
  Pierre Fraigniaud, Journal of Parallel and Distributed Computing, vol. 16, no. 1, p. 15-26, 1992

1991

• Arc-Disjoint Spanning Trees on Cube-Connected Cycles Networks
  P. Fraigniaud and C-T. Ho, International Conference on Parallel Processing (ICPP'91), 1991
• Broadcasting in a Hypercube when Some Calls Fail
  P. Fraigniaud and C. Peyrat, Information Processing Letters, vol. 39, p. 115-119, 1991
• Communications in Interconnection Networks
  J-C. Bermond and P. Fraigniaud, Workshop of Combinatorial Optimization in Science and Technology, 1991
• Fault-Tolerant Gossiping on Hypercube Multicomputer
  P. Fraigniaud, Distributed Memory Computing Conference, Lecture Notes in Computer Science 487, Arndt Bode Eds., Springer-Verlag, p. 463-472, 1991
• The Durand-Kerner Polynomials Root Finding Method in Case of Multiple Roots
  P. Fraigniaud, BIT, vol. 31, p. 112-123, 1991

1990

• A Performance Analysis of Network Topologies in Finding the Roots of a Polynomial
  M. Cosnard and P. Fraigniaud, COMPAR 90 - VAPP IV, Lecture Notes in Computer Science 457, H. Burkhart Eds., Springer-Verlag, p. 875-886, 1990
• Asynchronous Durand-Kerner and Aberth Polynomial Root Finding Methods on a Distributed Memory Multicomputer
  M. Cosnard and P. Fraigniaud, Parallel Computing 89, D.J.Evans, G.R.Joubert and F.J.Peters Eds., North Holland, p. 79-84, 1990
• Complexity of Scattering on a Ring of Processors
  P. Fraigniaud and S. Miguet and Y. Robert, 5th Distributed Memory Computing Conference, D. Walker and Q. Stout Eds., IEEE Computer Society Press, p. 1343-1347, 1990
• Finding the Roots of a Polynomial on an MIMD Multicomputer
  M. Cosnard and P. Fraigniaud, Parallel Computing, vol. 15, p. 75-85, 1990
• On the Analysis of Polynomials Roots-Finding Parallel Algorithms
  M. Cosnard and P. Fraigniaud, Parallel and Distributed Processing, K. Boyanov Eds., North-Holland, p. 243-262, 1990
• Scattering on a Ring of Processors
  P. Fraigniaud and S. Miguet and Y. Robert, Parallel Computing, vol. 13, p. 377-383, 1990

1989

• Performance Analysis of Broadcasting in Hypercubes
  P. Fraigniaud, Hypercubes and Distributed Computers, F.André and J.P.Verjus Eds., North Holland, p. 311-328, 1989