Expander properties and the cover time of random intersection graphs

DOI10.1016/J.TCS.2009.08.028MaRDI QIDQ1034533zbMATH OpenOpenAlexFDO

Authors Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, P. G. Spirakis

Publication date 6 November 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.08.028

zbMATH Keywords

expansionrandom walksmixing timecover timerandom intersection graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Expander Properties and the Cover Time of Random Intersection Graphs
• Expansion and the cover time of parallel random walks
• scientific article; zbMATH DE number 2079333
• Bounds on the cover time
• Random walks which prefer unvisited edges, exploring high girth even degree expanders in linear time

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• Algorithms and Computation
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating layout problems on random geometric graphs
• Automata, Languages and Programming
• Automata, Languages and Programming
• Automata, Languages and Programming
• Comparison theorems for reversible Markov chains
• Expander Properties and the Cover Time of Random Intersection Graphs
• Expander properties in random regular graphs with edge faults
• On Random Intersection Graphs: The Subgraph Problem
• On the Cover Time for Random Walks on Random Graphs
• Paths in graphs
• Random Geometric Graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• Sur deux propriétés des classes d'ensembles
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• The cover time of sparse random graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The vertex degree distribution of random intersection graphs

Cited in

(6)

• Sharp thresholds for Hamiltonicity in random intersection graphs
• On Some Combinatorial Properties of Random Intersection Graphs
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• On the chromatic number of non-sparse random intersection graphs
• Hyperbolicity, degeneracy, and expansion of random intersection graphs
• Expander Properties and the Cover Time of Random Intersection Graphs

This page was built for publication: Expander properties and the cover time of random intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034533)