Why Is Maximum Clique Often Easy in Practice?
From MaRDI portal
Publication:5144801
DOI10.1287/opre.2019.1970zbMath1457.90166OpenAlexW3035434998MaRDI QIDQ5144801
Austin Buchanan, Jose L. Walteros
Publication date: 19 January 2021
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.2019.1970
degeneracyvertex covermaximum cliqueparameterized complexitykernelization\(k\)-corefixed-parameter tractablefptparameterized below degeneracy
Related Items (11)
On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ A matheuristic for a customer assignment problem in direct marketing ⋮ Influence Maximization with Latency Requirements on Social Networks ⋮ Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set 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 ⋮ Worst-case analysis of clique MIPs ⋮ A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Infra-chromatic bound for exact maximum clique search
- A new exact maximum clique algorithm for large and massive sparse graphs
- Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
- Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
- A parallel maximum clique algorithm for large and massive sparse graphs
- Improved upper bounds for vertex cover
- Minimum degree orderings
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- An exact algorithm for the maximum clique problem
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Some simplified NP-complete graph problems
- The sandwich theorem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- A general method to speed up fixed-parameter-tractable algorithms
- A fast algorithm for the maximum clique problem
- A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition
- Exact algorithms for maximum clique: a computational study
- Vertex Cover: Further Observations and Further Improvements
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs
- Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks
- Minimum node covers and 2-bicritical graphs
- Emergence of Scaling in Random Networks
- A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
- Parallel Maximum Clique Algorithms with Applications to Network Analysis
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Set Partitioning via Inclusion-Exclusion
- Smallest-last ordering and clustering and graph coloring algorithms
- A Sufficient Condition for Backtrack-Free Search
- Vertex packings: Structural properties and algorithms
- On the Shannon capacity of a graph
- Nondeterminism within $P^ * $
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- CSDP, A C library for semidefinite programming
- The Linkage of a Graph
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- An enhanced bitstring encoding for exact maximum clique search in sparse graphs
- Linear-Time FPT Algorithms via Network Flow
- Models of Online Social Networks
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- On chromatic number of graphs and set-systems
- An inequality for the chromatic number of a graph
- k-Degenerate Graphs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Why Is Maximum Clique Often Easy in Practice?
