🔮
🔮
The Ethereal
The cover time of a biased random walk on a random cubic graph
January 02, 2018 · The Ethereal · 🏛 International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Colin Cooper, Alan Frieze, Tony Johansson
arXiv ID
1801.00760
Category
math.CO: Combinatorics
Cross-listed
cs.DS
Citations
7
Venue
International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms
Last Checked
2 months ago
Abstract
We study a random walk that prefers tou se unvisited edges in the context of random cubic graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being $\approx n\log n$ and $\approx \frac32n\log n$ respectively.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
📜 Similar Papers
In the same crypt — Combinatorics
🔮
🔮
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
🔮
🔮
The Ethereal
Generalized Twisted Gabidulin Codes
🔮
🔮
The Ethereal
Tables of subspace codes
🔮
🔮
The Ethereal
Classification of weighted networks through mesoscale homological features
🔮
🔮
The Ethereal