s'authentifier
version française rss feed

inria-00373850, version 1

A distributed algorithm for computing and updating the process number of a forest

David Coudert () a1, Florian Huc 12, Dorian Mazauric 1

22nd International Symposium on Distributed Computing (DISC) 5218 (2008) 500-501

Résumé : In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms.

  • Domaine : Informatique/Réseaux et télécommunications
    Informatique/Algorithme et structure de données
 
  • inria-00373850, version 1
  • oai:hal.inria.fr:inria-00373850
  • Contributeur : 
  • Déposé pour le compte de : 
  • Soumis le : Mardi 7 Avril 2009, 14:38:06
  • Dernière modification le : Mardi 7 Avril 2009, 14:49:53
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...