Name
Abstract | ||
|---|---|---|
Let P = G□H be the cartesian product of graphs G, H. We relate the cover time COV[P] of P to the cover times of its factors. When one of the factors is in some sense larger than the other, its cover time dominates, and can become of the same order as the cover time of the product as a whole. Our main theorem effectively gives conditions for when this holds. The probabilistic technique which we introduce, based on the blanket time, is more general and may be of independent interest, as might some of our lemmas. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-19222-7_37 | IWOCA |
Keywords | Field | DocType |
cover time cov,cartesian product graph,probabilistic technique,independent interest,graphs g,cover time,blanket time,main theorem,cartesian product,random walk,cartesian | Discrete mathematics,Product measure,Combinatorics,Direct product,Cartesian product,Random walk,Cartesian product of graphs,Product (mathematics),Probabilistic logic,Lemma (mathematics),Mathematics | Conference |
Volume | ISSN | Citations |
6460 | 0302-9743 | 3 |
PageRank | References | Authors |
0.45 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammed Abdullah | 1 | 4 | 0.81 |
| Colin Cooper | 2 | 857 | 91.88 |
| Tomasz Radzik | 3 | 1098 | 95.68 |