On the kernel size of clique cover reductions for random intersection graphs
From MaRDI portal
Publication:491163
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
parameterized algorithmskernelizationaverage caserandom intersection graphsErdős-Rényi graphsclique cover
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the kernel size of clique cover reductions for random intersection graphs
