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
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
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
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
- Algorithm 457: finding all cliques of an undirected graph
- Graph Partitioning and Graph Clustering
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Number of cliques in random scale-free network ensembles
Cited In (8)
- A polytime preprocess algorithm for the maximum independent set problem
- Listing all maximal cliques in large sparse real-world graphs
- Why is maximum clique often easy in practice?
- A new decomposition technique for maximal clique enumeration for sparse graphs
- Listing all maximal cliques in sparse graphs in near-optimal time
- 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
Uses Software
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)
