Solving maximum clique in sparse graphs: an O(nm+n2d/4) algorithm for d-degenerate graphs

DOI10.1007/S11590-013-0698-2MaRDI QIDQ479213zbMATH OpenOpenAlexFDO

Authors Austin Buchanan, Jose L. Walteros, Panos M. Pardalos, Sergiy Butenko

Publication date 5 December 2014

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-013-0698-2

zbMATH Keywords

degeneracymaximum cliquesparse graphstractability\(d\)-degenerate graphsfixed-parameter

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A new decomposition technique for maximal clique enumeration for sparse graphs
• A new exact maximum clique algorithm for large and massive sparse graphs
• A linear time algorithm for maximal clique enumeration in large sparse graphs
• Fast algorithms for the maximum clique problem on massive sparse graphs
• Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
• Fast maximal cliques enumeration in sparse graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• On CLIQUE Problem for Sparse Graphs of Large Dimension
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• An output sensitive algorithm for maximal clique enumeration in sparse graphs

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 5785643 (Why is no real title available?)
• k-Degenerate Graphs
• Algorithm 457: finding all cliques of an undirected graph
• Fast algorithms for max independent set
• Graph Partitioning and Graph Clustering
• Listing all maximal cliques in sparse graphs in near-optimal time
• Number of cliques in random scale-free network ensembles
• Smallest-last ordering and clustering and graph coloring algorithms

Cited in

(8)

• A polytime preprocess algorithm for the maximum independent set problem
• Listing all maximal cliques in large sparse real-world graphs
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• Why is maximum clique often easy in practice?
• Worst-case analysis of clique MIPs
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• General results on preferential attachment and clustering coefficient

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs

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