The Cover Time of Cartesian Product Graphs

DOI10.1007/978-3-642-19222-7_37zbMath1326.05146OpenAlexW1640308756MaRDI QIDQ3000524

Tomasz Radzik, Colin Cooper, Mohammed Amin Abdullah

Publication date: 19 May 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_37

zbMATH Keywords

random walksCartesian product graphscover timeeffective resistanceblanket time

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Unnamed Item
• Cover times, blanket times, and majorizing measures
• Random walks and electrical resistances in products of graphs
• Covering problems for Brownian motion on spheres
• The electrical resistance of a graph captures its commute and cover times
• An upper bound on the cover time for powers of graphs
• Cover times for Brownian motion and random walks in two dimensions
• Multiple cover time
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs