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

DOI10.1007/S11590-013-0698-2zbMATH Open1303.05184OpenAlexW80045804MaRDI QIDQ479213FDOQ479213

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithm 457: finding all cliques of an undirected graph
• Graph Partitioning and Graph Clustering
• Smallest-last ordering and clustering and graph coloring algorithms
• k-Degenerate Graphs
• Fast algorithms for max independent set
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Number of cliques in random scale-free network ensembles

Cited In (5)

• A polytime preprocess algorithm for the maximum independent set problem
• Why Is Maximum Clique Often Easy in Practice?
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Worst-case analysis of clique MIPs
• General results on preferential attachment and clustering coefficient

Uses Software

• Algorithm 457

Recommendations

• Title not available (Why is that?) 👍 👎
• Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs 👍 👎
• A new exact maximum clique algorithm for large and massive sparse graphs 👍 👎
• A new decomposition technique for maximal clique enumeration for sparse graphs 👍 👎
• Fast maximal cliques enumeration in sparse graphs 👍 👎
• Solving the maximum edge-weight clique problem in sparse graphs with compact formulations 👍 👎
• A linear time algorithm for maximal clique enumeration in large 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 👍 👎

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)