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