2017 · 25 citations · 38 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsParallel AlgorithmsParallel ComputingData ParallelismGraph AlgorithmsParallel ArchitecturesParallel Computer ArchitectureParallel Performance AnalysisShared-memory ParallelismClique AlgorithmsCliquesEnumeration Algorithms For GraphsGpu ArchitectureMulti-core ComputingParallel Graph AlgorithmsParallel OperationsShared-memory Algorithms
The enumeration of all maximal cliques in an undirected graph is a fundamental problem arising in several research areas. We consider maximal clique enumeration on shared-memory, multi-core architectures and introduce an approach consisting entirely of data-parallel operations, in an effort to achieve efficient and portable performance across different architectures. We study the performance of the algorithm via experiments varying over benchmark graphs and architectures. Overall, we observe that our algorithm achieves up to a 33-time speedup and 9-time speedup over state-of-the-art distributed and serial algorithms, respectively, for graphs with higher ratios of maximal cliques to total cliques. Further, we attain additional speedups on a GPU architecture, demonstrating the portable performance of our data-parallel design.
38
XSEDE: Accelerating Scientific Discovery
John Towns, T.M. Cockerill, Maytal Dahan et al. · Computing in Science & Engineering · 2014 · 3.3K citations · Full text
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text
J. W. Moon, Leo Moser · Israel Journal of Mathematics · 1965 · 854 citations
Arboricity and Subgraph Listing Algorithms
Norishige Chiba, Takao Nishizeki · SIAM Journal on Computing · 1985 · 665 citations