Efficiently covering complex networks with cliques of similar vertices

DOI10.1016/j.tcs.2005.12.005zbMath1088.68013OpenAlexW1968481794MaRDI QIDQ2368963

Michael Behrisch, Anusch Taraz

Publication date: 28 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.12.005

zbMATH Keywords

Random graphsIntersection graphsClique cover algorithm

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) 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)

Related Items (11)

Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ An overview of graph covering and partitioning ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Clique Cover and Graph Separation ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs ⋮ On the kernel size of clique cover reductions for random intersection graphs ⋮ \(0\text{-}1\) multilinear programming as a unifying theory for LAD pattern generation ⋮ Large-scale clique cover of real-world networks ⋮ Isolation concepts for clique enumeration: comparison and computational experiments ⋮ Connectivity of the uniform random intersection graph ⋮ Enumerating Isolated Cliques in Synthetic and Financial Networks

Uses Software

• COSMOS

Cites Work

• Unnamed Item
• Unnamed Item
• Component evolution in random intersection graphs
• Random interval graphs
• Bipartite structure of all complex networks
• Two Models of Random Intersection Graphs and their Applications
• On Random Intersection Graphs: The Subgraph Problem
• The vertex degree distribution of random intersection graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Coloring Random Intersection Graphs and Complex Networks

This page was built for publication: Efficiently covering complex networks with cliques of similar vertices