A $\tilde O(n^2)$ Time-Space Trade-off for Undirected s-t Connectivity

1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : In this paper, we make use of the Metropolis-type walks due to Nonaka et al. (2010) to provide a faster solution to the $S$-$T$-connectivity problem in undirected graphs (USTCON). As our main result, we propose a family of randomized algorithms for USTCON which achieves a time-space product of $S\cdot T = \tilde O(n^2)$ in graphs with $n$ nodes and $m$ edges (where the $\tilde O$-notation disregards poly-logarithmic terms). This improves the previously best trade-off of $\tilde O(n m)$, due to Feige (1995). Our algorithm consists in deploying several short Metropolis-type walks, starting from landmark nodes distributed using the scheme of Broder et al. (1994) on a modified input graph. In particular, we obtain an algorithm running in time $\tilde O(n+m)$ which is, in general, more space-efficient than both BFS and DFS. We close the paper by showing how to fine-tune the Metropolis-type walk so as to match the performance parameters (e.g., average hitting time) of the unbiased random walk for any graph, while preserving a worst-case bound of $\tilde O(n^2)$ on cover time.
Keywords :
Type de document :
Communication dans un congrès
SODA - 24th ACM-SIAM Symposium on Discrete Algorithms, Jan 2013, New Orleans, United States. SIAM, pp.1873-1883, 2013

https://hal.inria.fr/hal-00685373
Soumis le : mardi 10 juillet 2012 - 00:15:21
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 11 octobre 2012 - 02:55:07

Fichiers

fastrw.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : hal-00685373, version 3
• ARXIV : 1204.1136

Citation

Adrian Kosowski. A $\tilde O(n^2)$ Time-Space Trade-off for Undirected s-t Connectivity. SODA - 24th ACM-SIAM Symposium on Discrete Algorithms, Jan 2013, New Orleans, United States. SIAM, pp.1873-1883, 2013. 〈hal-00685373v3〉

Métriques

Consultations de la notice

538

Téléchargements de fichiers