On the kernel size of clique cover reductions for random intersection graphs

DOI10.1016/J.JDA.2015.05.014zbMath1336.05115OpenAlexW584368007MaRDI QIDQ491163

Tobias Friedrich, Christian Hercher

Publication date: 24 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.05.014

zbMATH Keywords

parameterized algorithmskernelizationaverage caserandom intersection graphsErdős-Rényi graphsclique cover

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

An overview of graph covering and partitioning ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple lower bound on edge coverings by cliques
• Algorithms for compact letter displays: comparison and evaluation
• On problems without polynomial kernels
• Can visibility graphs be represented compactly?
• Covering the edges of a random graph by cliques
• Parameterized clique on inhomogeneous random graphs
• On the average-case complexity of parameterized clique
• Clique coverings of the edges of a random graph
• Efficiently covering complex networks with cliques of similar vertices
• Bipartite structure of all complex networks
• Clique Cover and Graph Separation
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• On Random Intersection Graphs: The Subgraph Problem
• On the hardness of approximating minimization problems
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• Parameterized Clique on Scale-Free Networks
• Clique Cover on Sparse Networks
• Data reduction and exact algorithms for clique cover
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: On the kernel size of clique cover reductions for random intersection graphs