Expander properties and the cover time of random intersection graphs

DOI10.1016/j.tcs.2009.08.028zbMath1194.68174OpenAlexW2078953993MaRDI QIDQ1034533

Paul G. Spirakis, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos

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)

Related Items

On Some Combinatorial Properties of Random Intersection Graphs, On the chromatic number of non-sparse random intersection graphs, Sharp thresholds for Hamiltonicity in random intersection graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Comparison theorems for reversible Markov chains
• Approximating Layout Problems on Random Geometric Graphs
• The cover time of sparse random graphs
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• Expander Properties and the Cover Time of Random Intersection Graphs
• On the Cover Time for Random Walks on Random Graphs
• On Random Intersection Graphs: The Subgraph Problem
• Random Geometric Graphs
• Expander properties in random regular graphs with edge faults
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• The vertex degree distribution of random intersection graphs
• Paths in graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Automata, Languages and Programming
• Automata, Languages and Programming
• Automata, Languages and Programming
• Sur deux propriétés des classes d'ensembles
• Algorithms and Computation