Speeding up cover time of sparse graphs using local knowledge

DOI10.1007/978-3-319-29516-9_1MaRDI QIDQ2798211zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Moez Draief, Mohammed Abdullah

Publication date 4 April 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-29516-9_1

zbMATH Keywords

network explorationrandom graphsrandom walks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Recommendations

• Random walks with the minimum degree local rule have O(N^2) cover time
• Random walks with the minimum degree local rule have O(n^2) cover time
• The hitting and cover times of random walks on finite graphs using local degree information
• scientific article; zbMATH DE number 2079333
• Cover time of a random graph with given degree sequence

Cited in

(5)

• The hitting and cover times of random walks on finite graphs using local degree information
• Random walks with the minimum degree local rule have O(n^2) cover time
• Random walks with the minimum degree local rule have O(N^2) cover time
• Improved Local Computation Algorithm for Set Cover via Sparsification
• Reversible random walks on dynamic graphs

This page was built for publication: Speeding up cover time of sparse graphs using local knowledge

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