Geodesic
Cover time of a random graph with given degree sequence
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

Voir la notice de l'article provenant de la source Episciences

In this paper we establish the cover time of a random graph $G(\textbf{d})$ chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\textbf{d}$. We show that under certain restrictions on $\textbf{d}$, the cover time of $G(\textbf{d})$ is with high probability asymptotic to $\frac{d-1}{ d-2} \frac{\theta}{ d}n \log n$. Here $\theta$ is the average degree and $d$ is the $\textit{effective minimum degree}$. The effective minimum degree is the first entry in the sorted degree sequence which occurs order $n$ times. 
@article{DMTCS_2010_special_258_a40,
     author = {Abdullah, Mohammed and Cooper, Colin and Frieze, Alan},
     title = {Cover time of a random graph with given degree sequence},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2804},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2804/}
}
TY  - JOUR
AU  - Abdullah, Mohammed
AU  - Cooper, Colin
AU  - Frieze, Alan
TI  - Cover time of a random graph with given degree sequence
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2804/
DO  - 10.46298/dmtcs.2804
LA  - en
ID  - DMTCS_2010_special_258_a40
ER  - 
%0 Journal Article
%A Abdullah, Mohammed
%A Cooper, Colin
%A Frieze, Alan
%T Cover time of a random graph with given degree sequence
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2804/
%R 10.46298/dmtcs.2804
%G en
%F DMTCS_2010_special_258_a40
Abdullah, Mohammed; Cooper, Colin; Frieze, Alan. Cover time of a random graph with given degree sequence. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2804. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2804/

Cité par Sources :