Expander properties and the cover time of random intersection graphs

DOI10.1016/J.TCS.2009.08.028zbMATH Open1194.68174OpenAlexW2078953993MaRDI QIDQ1034533FDOQ1034533

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

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

zbMATH Keywords

expansionrandom walksmixing timecover timerandom intersection graphs

Mathematics Subject Classification ID

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

Cites Work

• Random Geometric Graphs
• On Random Intersection Graphs: The Subgraph Problem
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Paths in graphs
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Comparison theorems for reversible Markov chains
• The vertex degree distribution of random intersection 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
• Approximating layout problems on random geometric graphs
• Automata, Languages and Programming
• Sur deux propriétés des classes d'ensembles
• The cover time of sparse random graphs
• On the Cover Time for Random Walks on Random Graphs
• Algorithms and Computation
• Expander Properties and the Cover Time of Random Intersection Graphs
• Expander properties in random regular graphs with edge faults
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• Automata, Languages and Programming

Cited In (6)

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