Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring

DOI10.1007/BF01955041zbMath0846.68078OpenAlexW2053867237MaRDI QIDQ1913697

Jue Xue, Egon Balas

Publication date: 27 May 1996

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

minimum vertex coloring problemfractional coloring problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

A fast algorithm for the maximum clique problem ⋮ Iterative coloring extension of a maximum clique ⋮ Detecting robust cliques in graphs subject to uncertain edge failures ⋮ Reducing graph coloring to clique search ⋮ Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations ⋮ Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem ⋮ On the minimum number of logical clauses inferred from examples ⋮ Efficient pattern matching on big uncertain graphs ⋮ Solving hard set covering problems ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Combinatorial algorithms for the maximum \(k\)-plex problem ⋮ Co-2-plex vertex partitions ⋮ Solving the minimum-weighted coloring problem ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ An algorithm for finding a maximum clique in a graph ⋮ Estimating clique size by coloring the nodes of auxiliary graphs ⋮ The maximum clique problem

Cites Work

• Unnamed Item
• Unnamed Item
• Finding maximum cliques in arbitrary and in special graphs
• An exact algorithm for the maximum clique problem
• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
• An exact algorithm for the maximum stable set problem
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Finding a Maximum Clique in an Arbitrary Graph
• A graph coloring algorithm for large scheduling problems
• New methods to color the vertices of a graph
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• A branch and bound algorithm for the maximum clique problem

This page was built for publication: Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring