Fast algorithms for the maximum clique problem on massive sparse graphs

DOI10.1007/978-3-319-03536-9_13MaRDI QIDQ2938025zbMATH OpenOpenAlexFDO

Authors Bharath Pattabiraman, Md. Mostofa Ali Patwary, Wei-Keng Liao, Assefaw H. Gebremedhin, Alok Choudhary

Publication date 13 January 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5818

zbMATH Keywords

maximum cliquessparse graphs

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Internet topics (68M11)

Abstract: The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, informatics, and many other areas. Although there exist several algorithms with acceptable runtimes for certain classes of graphs, many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques to very quickly find maximum cliques in large sparse graphs. Extensive experiments on several types of synthetic and real-world graphs show that our new algorithm is up to several orders of magnitude faster than existing algorithms for most instances. We also present a heuristic variant that runs orders of magnitude faster than the exact algorithm, while providing optimal or near-optimal solutions.

Recommendations

• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• A new exact maximum clique algorithm for large and massive sparse graphs
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• Parallel maximum clique algorithms with applications to network analysis
• A parallel maximum clique algorithm for large and massive sparse graphs

Cited in

(19)

• Multi-threading a state-of-the-art maximum clique algorithm
• Computing maximum \(k\)-defective cliques in massive graphs
• Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• A new exact maximum clique algorithm for large and massive sparse graphs
• Parallel maximum clique algorithms with applications to network analysis
• On CLIQUE Problem for Sparse Graphs of Large Dimension
• Enumerating maximal cliques in large sparse graphs
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Why is maximum clique often easy in practice?
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• A parallel maximum clique algorithm for large and massive sparse graphs
• An enhanced bitstring encoding for exact maximum clique search in sparse graphs
• Solving larger maximum clique problems using parallel quantum annealing
• Machine learning predicts graph properties: clique, girth, and independent numbers

Describes a project that uses

Uses Software

• SparseMatrix

This page was built for publication: Fast algorithms for the maximum clique problem on massive sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938025)