Loading [MathJax]/jax/output/HTML-CSS/jax.js

Mohammed Abdullah ; Colin Cooper ; Alan Frieze - Cover time of a random graph with given degree sequence

dmtcs:2804 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2804
Cover time of a random graph with given degree sequenceConference paper

Authors: Mohammed Abdullah 1; Colin Cooper 1; Alan Frieze ORCID2

  • 1 Department of Computer Science
  • 2 Department of Mathematical Sciences [Pittsburgh]

In this paper we establish the cover time of a random graph G(d) chosen uniformly at random from the set of graphs with vertex set [n] and degree sequence d. We show that under certain restrictions on d, the cover time of G(d) is with high probability asymptotic to d1d2θdnlogn. Here θ is the average degree and d is the effective minimum degree. The effective minimum degree is the first entry in the sorted degree sequence which occurs order n times.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Random walks,random graphs,cover time,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • Probabilistic Considerations in the Analysis of Algorithms; Funder: National Science Foundation; Code: 0502793

14 Documents citing this article

Consultation statistics

This page has been seen 328 times.
This article's PDF has been downloaded 420 times.