Random walks on colored graphs

DOI10.1002/RSA.3240050204MaRDI QIDQ4286296zbMATHOpenAlexFDO

Authors Anne Condon, Diane Hernek

Publication date 27 March 1994

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240050204

zbMATH Keywords

random walksstochastic matricesundirected graphscover timetime-inhomogeneous Markov chainsdominant eigenvectorscolored edges

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the cover time of random walks on graphs
• scientific article; zbMATH DE number 878897
• Bounds on the cover time
• Multiple cover time
• How Well Do Random Walks Parallelize?

Cites work

• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Definite and Quasidefinite Sets of Stochastic Matrices
• Eigenvalues and expanders
• Finite state verifiers I
• Non-negative matrices and Markov chains.
• Products of Indecomposable, Aperiodic, Stochastic Matrices
• Proof of Shannon's Transmission Theorem for Finite-State Indecomposable Channels
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded probabilistic game automata

Cited in

(6)

• Painting a graph with competing random walks
• Random walk in a finite directed graph subject to a road coloring
• Edge flipping in graphs
• The relevant prefixes of coloured Motzkin walks: an average case analysis
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities
• Toward a theory of Markov influence systems and their renormalization

This page was built for publication: Random walks on colored graphs

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