Finding maximum cliques in arbitrary and in special graphs

DOI10.1007/BF02257777zbMath0731.05029OpenAlexW1512959368MaRDI QIDQ807639

Luitpold Babel

Publication date: 1991

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02257777

zbMATH Keywords

branch and bound algorithmmaximum clique problempolynomial solvable problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A fast algorithm for the maximum clique problem, An exact algorithm for the maximum stable set problem, A multi-KP modeling for the maximum-clique problem, Iterative coloring extension of a maximum clique, Novel evolutionary models and applications to sequence alignment problems, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, On the minimum number of logical clauses inferred from examples, An extended formulation for the 1‐wheel inequalities of the stable set polytope, Solving the minimum-weighted coloring problem, Clique-detection models in computational biochemistry and genomics, Finding all \(k\)-cliques in \(k\)-partite graphs, an application in textile engineering, An algorithm for finding a maximum clique in a graph, A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles, A network-flow-based lower bound for the minimum weighted integer coloring problem, A fast algorithm for the maximum weight clique problem, The maximum clique problem

Uses Software

• TABARIS
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
• A new backtracking algorithm for generating the family of maximal independent sets of a graph
• On maximal independent sets of vertices in claw-free graphs
• Clique detection for nondirected graphs: Two new algorithms
• Incidence matrices and interval graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Efficient algorithms for finding maximum cliques of an overlap graph
• A Linear Recognition Algorithm for Cographs
• Finding a Maximum Clique in an Arbitrary Graph
• The NP-completeness column: an ongoing guide
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Stability in circular arc graphs
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Finding maximum cliques in circle graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Determining the number of internal stability of a graph
• Algorithms on circular-arc graphs
• Vertex packings: Structural properties and algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Finding a Maximum Independent Set
• A node covering algorithm
• New methods to color the vertices of a graph
• 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
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithm 457: finding all cliques of an undirected graph
• A branch and bound algorithm for the maximum clique problem
• The NP-completeness column: An ongoing guide