Maximum cliques in graphs with small intersection number and random intersection graphs

DOI10.1016/j.cosrev.2020.100353zbMath1487.05198arXiv1204.4054OpenAlexW3115081644MaRDI QIDQ826323

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

Publication date: 20 December 2021

Published in: Computer Science Review, Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.4054

zbMATH Keywords

intersection numbermaximum cliquerandom intersection graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ On Some Combinatorial Properties of Random Intersection Graphs ⋮ Selected combinatorial problems through the prism of random intersection graphs models ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs ⋮ On the chromatic number of non-sparse random intersection graphs ⋮ Large cliques in sparse random intersection graphs ⋮ Paired threshold graphs

Cites Work

• Unnamed Item
• Large cliques in sparse random intersection graphs
• On the independence number and Hamiltonicity of uniform random intersection graphs
• The chromatic and clique numbers of random scaled sector graphs
• Maximum cliques in graphs with small intersection number and random intersection graphs
• Strong computational lower bounds via parameterized complexity
• Approximating the independence number via the \(\vartheta\)-function
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Efficiently covering complex networks with cliques of similar vertices
• Bounds on the bisection width for random \(d\)-regular graphs
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• Equivalence of a random intersection graph and G (n ,p )
• A spectral heuristic for bisecting random graphs
• Algorithms for maximum independent sets
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• On Random Intersection Graphs: The Subgraph Problem
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Approximating Maximum Clique by Removing Subgraphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Reducibility among Combinatorial Problems
• Coloring Random Intersection Graphs and Complex Networks
• Approximating layout problems on random graphs

This page was built for publication: Maximum cliques in graphs with small intersection number and random intersection graphs