Random walks on colored graphs

DOI10.1002/RSA.3240050204zbMATH Open0792.05123OpenAlexW2169846294MaRDI QIDQ4286296FDOQ4286296

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

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?

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)

Cites Work

• Eigenvalues and expanders
• Non-negative matrices and Markov chains.
• Relationships between nondeterministic and deterministic tape complexities
• Title not available (Why is that?)
• Products of Indecomposable, Aperiodic, Stochastic Matrices
• Title not available (Why is that?)
• Finite state verifiers I
• Definite and Quasidefinite Sets of Stochastic Matrices
• Space-bounded probabilistic game automata
• Proof of Shannon's Transmission Theorem for Finite-State Indecomposable Channels

Cited In (5)

• Toward a Theory of Markov Influence Systems and their Renormalization
• The relevant prefixes of coloured Motzkin walks: an average case analysis
• Random walk in a finite directed graph subject to a road coloring
• Painting a graph with competing random walks
• Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities

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)