Simulating random walks on graphs in the streaming model

DOI10.4230/LIPICS.ITCS.2019.46MaRDI QIDQ5090424zbMATH OpenFDO

Authors Ce Jin

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1811.08205

zbMATH Keywords

random walkssamplingstreaming models

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Estimating PageRank on graph streams
• Automata, Languages and Programming
• On graph problems in a semi-streaming model
• Graph distances in the streaming model: the value of space
• Estimating graph parameters from random order streams

Cites work

• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• An improved data stream summary: the count-min sketch and its applications
• Approximating the Permanent
• Better bounds for matchings in the streaming model
• Better streaming algorithms for clustering problems
• Estimating PageRank on graph streams
• Finding repeated elements
• Finding sparse cuts locally using evolving sets
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• Improved approximation guarantees for weighted matching in the semi-streaming model
• Linear programming in the semi-streaming model with application to the maximum matching problem
• On data structures and asymmetric communication complexity
• Random generation of combinatorial structures from a uniform distribution
• Single pass spectral sparsification in dynamic streams
• Spectral sparsification in the semi-streaming setting
• Undirected connectivity in log-space
• Using PageRank to Locally Partition a Graph

Cited in

(2)

• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• New algorithms and lower bounds for streaming tournaments

This page was built for publication: Simulating random walks on graphs in the streaming model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090424)