Sublinear Fully Distributed Partition with ...
Type de document :
Article dans une revue scientifique
Titre :
Sublinear Fully Distributed Partition with Applications
Auteur(s) :
Derbel, Bilel [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Mosbah, Mohamed [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Zemmari, Akka [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Mosbah, Mohamed [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Zemmari, Akka [Auteur]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Titre de la revue :
Theory of Computing Systems
Pagination :
368-404
Éditeur :
Springer Verlag
Date de publication :
2010
ISSN :
1432-4350
Discipline(s) HAL :
Informatique [cs]/Autre [cs.OH]
Résumé en anglais : [en]
We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with $n$ nodes into a disjoint set of connected clusters with radius at most $k-1$ and having $O(n^{1+1/k})$ intercluster ...
Lire la suite >We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with $n$ nodes into a disjoint set of connected clusters with radius at most $k-1$ and having $O(n^{1+1/k})$ intercluster edges. We show how to implement our algorithms in the distributed $\mathcal{CONGEST}$ model of computation, i.e., limited message size, which improves the time complexity of previous algorithms~\cite{MS00,Awe85,Peleg00b} from $O(n)$ to $O(n^{1-1/k})$. We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the $\mathcal{CONGEST}$ model.Lire moins >
Lire la suite >We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with $n$ nodes into a disjoint set of connected clusters with radius at most $k-1$ and having $O(n^{1+1/k})$ intercluster edges. We show how to implement our algorithms in the distributed $\mathcal{CONGEST}$ model of computation, i.e., limited message size, which improves the time complexity of previous algorithms~\cite{MS00,Awe85,Peleg00b} from $O(n)$ to $O(n^{1-1/k})$. We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the $\mathcal{CONGEST}$ model.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://api.istex.fr/ark:/67375/VQC-7MV4LGLJ-F/fulltext.pdf?sid=hal
- Accès libre
- Accéder au document
- https://api.istex.fr/ark:/67375/VQC-7MV4LGLJ-F/fulltext.pdf?sid=hal
- Accès libre
- Accéder au document
- https://api.istex.fr/ark:/67375/VQC-7MV4LGLJ-F/fulltext.pdf?sid=hal
- Accès libre
- Accéder au document
- https://api.istex.fr/ark:/67375/VQC-7MV4LGLJ-F/fulltext.pdf?sid=hal
- Accès libre
- Accéder au document
- fulltext.pdf
- Accès libre
- Accéder au document