Parallel Maximum Clique Algorithms with Applications to Network Analysis

DOI10.1137/14100018XzbMath1323.05103OpenAlexW1823437338MaRDI QIDQ3447472

David F. Gleich, Ryan Anthony Rossi, Assefaw Hadish Gebremedhin

Publication date: 27 October 2015

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/14100018x

zbMATH Keywords

branch-and-boundnetwork analysisgraph compressionparallel maximum clique algorithmstemporal strong components

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ A maximum clique based approximation algorithm for wireless link scheduling under SINR model ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Worst-case analysis of clique MIPs

Uses Software

• igraph
• DIMACS
• IsoRank
• MaxCliqueDyn
• UbiCrawler
• Algorithm 457
• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact bit-parallel algorithm for the maximum clique problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• The maximum clique problem
• A fast algorithm for the maximum clique problem
• What's in a crowd? Analysis of face-to-face behavioral networks
• Exact algorithms for maximum clique: a computational study
• Multi-threading a state-of-the-art maximum clique algorithm
• Fast algorithms for determining (generalized) core groups in social networks
• Components in time-varying graphs
• Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Speeding Up Algorithms on Compressed Web Graphs
• Using Polynomial Chaos to Compute the Influence of Multiple Random Surfers in the PageRank Model
• Codes for the World Wide Web
• On chromatic number of graphs and set-systems
• Über eine von H. S. WILF angegebene Schranke für die chromatische Zahl endlicher Graphen
• Algorithm 457: finding all cliques of an undirected graph
• Benchmarking optimization software with performance profiles.

This page was built for publication: Parallel Maximum Clique Algorithms with Applications to Network Analysis