Why is maximum clique often easy in practice?
From MaRDI portal
Recommendations
- Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
- Listing all maximal cliques in large sparse real-world graphs
- On comparing algorithms for the maximum clique problem
- Listing all maximal cliques in sparse graphs in near-optimal time
- scientific article; zbMATH DE number 5997363
Cites work
- k-Degenerate Graphs
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
- A fast algorithm for the maximum clique problem
- A general method to speed up fixed-parameter-tractable algorithms
- A new exact maximum clique algorithm for large and massive sparse graphs
- A parallel maximum clique algorithm for large and massive sparse graphs
- A simple and faster branch-and-bound algorithm for finding a maximum clique
- A Sufficient Condition for Backtrack-Free Search
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- An enhanced bitstring encoding for exact maximum clique search in sparse graphs
- An exact algorithm for the maximum clique problem
- An improved branch and bound algorithm for the maximum clique problem
- An improved fixed-parameter algorithm for vertex cover
- An inequality for the chromatic number of a graph
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- CSDP, A C library for semidefinite programming
- Emergence of Scaling in Random Networks
- Exact algorithms for maximum clique: a computational study
- Fast algorithms for the maximum clique problem on massive sparse graphs
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 6118217 (Why is no real title available?)
- scientific article; zbMATH DE number 3889282 (Why is no real title available?)
- scientific article; zbMATH DE number 1424314 (Why is no real title available?)
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- Improved upper bounds for vertex cover
- Infra-chromatic bound for exact maximum clique search
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Linear-time FPT algorithms via network flow
- Listing all maximal cliques in large sparse real-world graphs
- Minimum degree orderings
- Minimum node covers and 2-bicritical graphs
- Models of online social networks
- Nondeterminism within $P^ * $
- On chromatic number of graphs and set-systems
- On the Shannon capacity of a graph
- Parallel maximum clique algorithms with applications to network analysis
- Parameterized algorithms
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Set partitioning via inclusion-exclusion
- Smallest-last ordering and clustering and graph coloring algorithms
- Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
- Solving the maximum clique and vertex coloring problems on very large sparse networks
- Some simplified NP-complete graph problems
- The Linkage of a Graph
- The sandwich theorem
- Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
Cited in
(16)- Worst-case analysis of clique MIPs
- A matheuristic for a customer assignment problem in direct marketing
- On Fault-Tolerant Low-Diameter Clusters in Graphs
- Influence maximization with latency requirements on social networks
- Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem
- Graph-Theoretic Concepts in Computer Science
- A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
- On atomic cliques in temporal graphs
- Research trends in combinatorial optimization
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
- A polytime preprocess algorithm for the maximum independent set problem
- CliSAT: a new exact algorithm for hard maximum clique problems
- Ultra-small world detection in networks: subgraphs with prescribed distance distributions
- Learning-augmented maximum independent set
- On the external validity of average-case analyses of graph algorithms
- Hyperbolic random graphs: clique number and degeneracy with implications for colouring
Describes a project that uses
Uses Software
This page was built for publication: Why is maximum clique often easy in practice?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144801)
