Random walks on some basic classes of digraphs

DOI10.1007/978-3-642-39718-9_8MaRDI QIDQ2851903zbMATH OpenOpenAlexFDO

Authors Wen-Ju Cheng, Jim Cox, Stathis Zachos

Publication date 4 October 2013

Published in Theoretical Aspects of Computing – ICTAC 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39718-9_8

zbMATH Keywords

BPLdigraph searchLNLrandom walksreachabilityRLspace-bounded complexity classesstrong connectivitysymmetric computation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Random walks on graphs (05C81) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Recommendations

• Pseudorandom walks on regular digraphs and the RL vs. L problem
• s-t connectivity on digraphs with a known stationary distribution
• Undirected connectivity in log-space
• Stationary distribution and cover time of random walks on random digraphs
• The Cover Time of Random Digraphs

Cited in

(4)

• Random walks on graphs and Monte Carlo methods
• Random walk on sparse random digraphs
• Walks and cycles on a digraph with application to population dynamics
• Pseudorandom walks on regular digraphs and the RL vs. L problem

This page was built for publication: Random walks on some basic classes of digraphs

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