mirage

Browsing by Author "Fraigniaud, Pierre"

DSpace/Manakin Repository

Browsing by Author "Fraigniaud, Pierre"

Sort by: Order: Results:

  • Approximation algorithms for information dissemination problems.
    Laboratoire de l'informatique du parallélisme; Fraigniaud, Pierre; Vial, Sandrine (1995-09)
    (eng) Broadcasting and gossiping are known to be NP-hard problems. This paper deals with approximation algorithms for such problems. We consider both round-complexity and step-complexity in the telephone model. After an ...
  • A Doubling dimension Threshold !(log log n) for augmented graph navigability
    Fraigniaud, Pierre; Lebhar, Emmanuelle; Lotker, Zvi; Laboratoire de l'informatique du parallélisme (LIP, 2006-02)
    In his seminal work, Klein leinberg showed how to augment meshes using randoom edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. ...
  • A Doubling dimension Threshold $\Theta(\log\log n)$ for augmented graph navigability
    Fraigniaud, Pierre; Lebhar, Emmanuelle; Lotker, Zvi; Laboratoire de l'informatique du parallélisme (LIP, 2006-04)
    (eng) In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. ...
  • Length and Number of Buses for Gossiping in Networks
    Laboratoire de l'informatique du parallélisme; Fraigniaud, Pierre; Laforest, Christian (1994-09-21)
    (eng) Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all the other nodes. A bus network is a network of processing ...
  • Local memory requirement of universal routing schemes.
    Laboratoire de l'informatique du parallélisme; Fraigniaud, Pierre; Gavoille, Cyril (1996-01)
    (eng) In this paper, we deal with the compact routing problem, that is the problem of implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all ...
Bookmark and Share