Large independent sets in general random intersection graphs

DOI10.1016/j.tcs.2008.06.047zbMath1151.68044OpenAlexW2029907394MaRDI QIDQ952443

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

Publication date: 12 November 2008

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

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

zbMATH Keywords

randomized algorithmindependent setwireless sensor networksrandom intersection graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

Networks beyond pairwise interactions: structure and dynamics ⋮ Random subcube intersection graphs. I: Cliques and covering ⋮ Unnamed Item ⋮ Constructions of independent sets in random intersection graphs ⋮ Colouring Non-sparse Random Intersection Graphs ⋮ On Some Combinatorial Properties of Random Intersection Graphs ⋮ Unnamed Item ⋮ Perfect matchings in random intersection graphs ⋮ Phase transitions for detecting latent geometry in random graphs ⋮ Large independent sets in general random intersection graphs ⋮ On the chromatic number of non-sparse random intersection graphs ⋮ The coupling method for inhomogeneous random intersection graphs. ⋮ Selected Combinatorial Properties of Random Intersection Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Large independent sets in general random intersection graphs
• Approximating Layout Problems on Random Geometric Graphs
• Expander Properties and the Cover Time of Random Intersection 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
• Paths in graphs
• Automata, Languages and Programming
• Sur deux propriétés des classes d'ensembles

This page was built for publication: Large independent sets in general random intersection graphs