Large independent sets in general random intersection graphs

DOI10.1016/J.TCS.2008.06.047MaRDI QIDQ952443zbMATH OpenOpenAlexFDO

Authors Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, P. 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Automata, Languages and Programming
• Constructions of independent sets in random intersection graphs
• Large cliques in sparse random intersection graphs
• Experimental and Efficient Algorithms

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1093829 (Why is no real title available?)
• scientific article; zbMATH DE number 1857648 (Why is no real title available?)
• Approximating layout problems on random geometric graphs
• Automata, Languages and Programming
• Expander Properties and the Cover Time of Random Intersection Graphs
• Expander properties in random regular graphs with edge faults
• Large independent sets in general random intersection graphs
• On Random Intersection Graphs: The Subgraph Problem
• Paths in graphs
• Random Geometric Graphs
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• Sur deux propriétés des classes d'ensembles
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(17)

• Networks beyond pairwise interactions: structure and dynamics
• Colouring Non-sparse Random Intersection Graphs
• Selected Combinatorial Properties of Random Intersection Graphs
• On Some Combinatorial Properties of Random Intersection Graphs
• Poisson approximation of induced subgraph counts in an inhomogeneous random intersection graph model
• Perfect matchings in random intersection graphs
• Constructions of independent sets in random intersection graphs
• Random subcube intersection graphs. I: Cliques and covering
• Large cliques in sparse random intersection graphs
• Large independent sets in general random intersection graphs
• Phase transitions for detecting latent geometry in random graphs
• Automata, Languages and Programming
• Balance in random signed intersection graphs
• Maximal Intersection Queries in Randomized Graph Models
• On the chromatic number of non-sparse random intersection graphs
• Large independent sets in regular graphs of large girth
• The coupling method for inhomogeneous random intersection graphs.

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

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