A spectral algorithm for finding maximum cliques in dense random intersection graphs
DOI10.1007/978-3-031-23101-8_2zbMath1529.68198arXiv2210.02121OpenAlexW4313429660MaRDI QIDQ6114455
Christoforos L. Raptopoulos, Filippos Christodoulou, Paul G. Spirakis, Sotiris E. Nikoletseas
Publication date: 14 August 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.02121
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Unnamed Item
- On the kernel size of clique cover reductions for random intersection graphs
- Large cliques in sparse random intersection graphs
- Maximum cliques in graphs with small intersection number and random intersection graphs
- Strong computational lower bounds via parameterized complexity
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Efficiently covering complex networks with cliques of similar vertices
- Equivalence of a random intersection graph and G (n ,p )
- Selected Combinatorial Properties of Random Intersection Graphs
- On colouring random graphs
- On Random Intersection Graphs: The Subgraph Problem
- Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
- Reducibility among Combinatorial Problems
This page was built for publication: A spectral algorithm for finding maximum cliques in dense random intersection graphs
