The maximum clique problem
From MaRDI portal
Publication:1318271
DOI10.1007/BF01098364zbMath0797.90108OpenAlexW4211250195WikidataQ90163273 ScholiaQ90163273MaRDI QIDQ1318271
Publication date: 27 March 1994
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01098364
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
A fast algorithm for the maximum clique problem, Subgraph extraction and metaheuristics for the maximum clique problem, On characterization of maximal independent sets via quadratic optimization, An exact algorithm for the maximum stable set problem, Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs, Maximum weighted induced subgraphs, A spinorial formulation of the maximum clique problem of a graph, Balanced independent and dominating sets on colored interval graphs, Communicability graph and community structures in complex networks, Parallel Maximum Clique Algorithms with Applications to Network Analysis, Problems of discrete optimization: challenges and main approaches to solve them, On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications, Applications and Computational Advances for Solving the QUBO Model, Complexity and Polynomially Solvable Special Cases of QUBO, Building an iterative heuristic solver for a quantum annealer, Exact algorithms for the minimum cost vertex blocker clique problem, A review on algorithms for maximum clique problems, Unnamed Item, On enumerating all minimal solutions of feedback problems, Finding disjoint dense clubs in a social network, An Efficient Approximation Algorithm for Finding a Maximum Clique Using Hopfield Network Learning, A variable neighborhood search heuristic for the maximum ratio clique problem, On a continuous approach for the maximum weighted clique problem, The worst-case time complexity for generating all maximal cliques and computational experiments, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, An adaptive multistart tabu search approach to solve the maximum clique problem, Solving the anti-covering location problem using Lagrangian relaxation, Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation, A potential reduction approach to the frequency assignment problem, On the minimum number of logical clauses inferred from examples, Diversification strategies in tabu search algorithms for the maximum clique problem, Metaheuristics: A bibliography, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, The maximum independent union of cliques problem: complexity and exact approaches, LP-based dual bounds for the maximum quasi-clique problem, The stable set problem: clique and nodal inequalities revisited, Diversification-driven tabu search for unconstrained binary quadratic problems, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Packing problems, dimensions and the tensor product of complete lattices, Solving maximum clique problem using chemical reaction optimization, The unconstrained binary quadratic programming problem: a survey, An exact algorithm for the maximum probabilistic clique problem, On risk-averse maximum weighted subgraph problems, On maximum ratio clique relaxations, Exact Solution Algorithms for the Chordless Cycle Problem, On designing networks resilient to clique blockers, Unnamed Item, On optimization problems in acyclic hypergraphs, Unnamed Item, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems, Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications, Solving unconstrained binary quadratic programming problem by global equilibrium search, Finding Disjoint Dense Clubs in an Undirected Graph, A sequential elimination algorithm for computing bounds on the clique number of a graph, Exact algorithms for maximum clique: a computational study, On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs, Neural networks for NP-complete problems, A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs, Recognition of split-graphic sequences, Geometry of the copositive and completely positive cones, Exploiting semidefinite relaxations in constraint programming, A quadratic programming approach to the determination of an upper bound on the weighted stability number, Variable neighborhood search for the maximum clique, Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem, Foundations of Set-Semidefinite Optimization, Finding clique clusters with the highest betweenness centrality, Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound, Gene selection via a new hybrid ant colony optimization algorithm for cancer classification in high-dimensional data, Detecting a most closeness-central clique in complex networks, Algorithms for finding maximum transitive subtournaments, Convex optimization for the densest subgraph and densest submatrix problems, Global equilibrium search applied to the unconstrained binary quadratic optimization problem, Interesting pattern mining in multi-relational data, Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, Quantum bridge analytics. I: A tutorial on formulating and using QUBO models, DISCOVERING PAIRWISE COMPATIBILITY GRAPHS, Exact bounds on the order of the maximum clique of a graph., An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph, Lagrangean decompositions for the unconstrained binary quadratic programming problem, An algorithm for finding a maximum clique in a graph, Strengthened clique-family inequalities for the stable set polytope, On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, The life span method -- a new variant of local search, Facets for node packing, Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection, Pairwise compatibility graphs, Reactive and dynamic local search for max-clique: engineering effective building blocks, Construction of constant GC-content DNA codes via a variable neighbourhood search algorithm, Dynamic node packing, Test case generators and computational results for the maximum clique problem, One-pass heuristics for large-scale unconstrained binary quadratic problems, A note on greedy algorithms for the maximum weighted independent set problem, A Python hands-on tutorial on network and topological neuroscience, Modelling competitive Hopfield networks for the maximum clique problem, An unconstrained quadratic binary programming approach to the vertex coloring problem
Uses Software
Cites Work
- Which claw-free graphs are perfectly orderable?
- TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
- Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
- On linear systems with integral valued solutions
- On rigid circuit graphs
- A new backtracking algorithm for generating the family of maximal independent sets of a graph
- Lower bounds for the clique and the chromatic numbers of a graph
- Weakly triangulated graphs
- Finding maximum cliques in arbitrary and in special graphs
- An efficient parallel algorithm for computing a large independent set in a planar graph
- Active constraints, indefinite quadratic test problems, and complexity
- On the complexity of test case generation for NP-hard problems
- An exact algorithm for the maximum clique problem
- On the independence number of random graphs
- The maximum number of cliques in dense graphs
- Random near-regular graphs and the node packing problem
- Clique numbers of graphs
- Relaxations of vertex packing
- Spectral bounds for the clique and independence numbers of graphs
- A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
- Constrained global optimization: algorithms and applications
- Matrices with the Edmonds-Johnson property
- Optima of dual integer linear programs
- The number of maximal independent sets in a connected graph
- On generating all maximal independent sets
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Weak bipolarizable graphs
- On maximal independent sets of vertices in claw-free graphs
- Structure preserving reductions among convex optimization problems
- Clique detection for nondirected graphs: Two new algorithms
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Polytope des independants d'un graphe série-parallèle
- A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically
- The ellipsoid method and its consequences in combinatorial optimization
- On stable set polyhedra for K//(1,3)free graphs
- Dual quadratic estimates in polynomial and Boolean programming
- Computing independent sets in graphs with large girth
- A note on the approximation of the MAX CLIQUE problem
- Finding a maximum set of independent chords in a circle
- A simple lower bound for monotone clique using a communication game
- On the diameter of convex polytopes
- Approximating maximum independent sets by excluding subgraphs
- Stability number of bull- and chair-free graphs
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
- Geometric algorithms and combinatorial optimization
- Approximation algorithms for combinatorial problems
- Clique detection in directed graphs: A new algorithm
- A class of facet producing graphs for vertex packing polyhedra
- On the perfect graph conjecture
- STABULUS: A technique for finding stable sets in large graphs with tabu search
- Test case generators and computational results for the maximum clique problem
- On certain polytopes associated with graphs
- Optimizing weakly triangulated graphs
- Lower bounds on the independence number in terms of the degrees
- Clique partitions, graph compression and speeding-up algorithms
- Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
- Solving the maximum clique problem using a tabu search approach
- Maximum internally stable sets of a graph
- Triangulated graphs and the elimination process
- Über iterierte Clique-Graphen
- A combinatorial approach for Keller's conjecture
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Über lückenlose Ausfüllung des \(n\)-dimensionalen Raumes durch kongruente Würfel
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- On the probable behaviour of some algorithms for finding the stability number of a graph
- Minimum node covers and 2-bicritical graphs
- A new table of constant weight codes
- Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- A clique-detection algorithm based on neighborhoods in graphs
- Covers and packings in a family of sets
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Efficient algorithms for finding maximum cliques of an overlap graph
- Degree-two Inequalities, Clique Facets, and Biperfect Graphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- Arboricity and Subgraph Listing Algorithms
- The Number of Maximal Independent Sets in a Tree
- Hard Enumeration Problems in Geometry and Combinatorics
- Finding a Maximum Clique in an Arbitrary Graph
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- On the Maximum Weight Clique Problem
- Improving the performance guarantee for approximate graph coloring
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A fast parallel algorithm for the maximal independent set problem
- Algorithms for maximum independent sets
- An approximation algorithm for the maximum independent set problem in cubic planar graphs
- A Note on Independent Sets in Trees
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- The number of maximal independent sets in connected graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Stability in circular arc graphs
- Expected Computation Time for Hamiltonian Path problem
- On graphs with polynomially solvable maximum-weight clique problem
- The maximum independent set problem for cubic planar graphs
- A New Parallel Algorithm for the Maximal Independent Set Problem
- The Complexity of Enumeration and Reliability Problems
- Some Ramsey-Type Numbers and the Independence Ratio
- (1,k)-configurations and facets for packing problems
- A Separator Theorem for Planar Graphs
- A Greedy Heuristic for the Set-Covering Problem
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
- Applications of a Planar Separator Theorem
- Finding maximum cliques in circle graphs
- An upper bound on the size of the largest cliques in a graph
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Determining the number of internal stability of a graph
- An algorithm for the maximum internally stable set in a weighted graph
- Design and Implementation of an Interactive Optimization System for Telephone Network Planning
- Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
- A global optimization approach for solving the maximum clique problem
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Keller’s cube-tiling conjecture is false in high dimensions
- Algorithms on circular-arc graphs
- Vertex packings: Structural properties and algorithms
- Cliques in random graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Finding a Maximum Independent Set
- On the integer-valued variables in the linear vertex packing problem
- A New Algorithm for Generating All the Maximal Independent Sets
- On the independence ratio of a graph
- A node covering algorithm
- An Algorithm for the Vertex Packing Problem
- New methods to color the vertices of a graph
- Determining the Stability Number of a Graph
- On the Shannon capacity of a graph
- Cliques of a graph-variations on the Bron-Kerbosch algorithm
- Covering, Packing and Knapsack Problems
- Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
- Computing and Combinatorics
- Constructing a Maximal Independent Set in Parallel
- An algorithm for finding a large independent set in planar graphs
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- Properties of vertex packing and independence system polyhedra
- Algebraic Tiling
- On the facial structure of set packing polyhedra
- Maxima for Graphs and a New Proof of a Theorem of Turán
- An Analysis of Some Graph Theoretical Cluster Techniques
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Corrections to Bierstone's Algorithm for Generating Cliques
- Upper Bounds on the Order of a Clique of a Graph
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Algorithm 457: finding all cliques of an undirected graph
- On Some Clustering Techniques
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- On the theory of graphs
- Hard graphs for the maximum clique problem
- A branch and bound algorithm for the maximum clique problem
- A branch and bound algorithm for the maximum clique problem
- On cliques in graphs
- On cliques in graphs
