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

DOI10.1007/BF01955041zbMATH Open0846.68078OpenAlexW2053867237MaRDI QIDQ1913697FDOQ1913697

Authors: E. Balas, Jue Xue 

Publication date: 27 May 1996

Published in: Algorithmica (Search for Journal in Brave)

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

Recommendations

• A fast algorithm for the maximum weight clique problem
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• New lower bounds on the weighted chromatic number of a graph
• A new algorithm for the maximum-weight clique problem
• Solving the minimum-weighted coloring problem

zbMATH Keywords

minimum vertex coloring problemfractional coloring problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A graph coloring algorithm for large scheduling problems
• New methods to color the vertices of a graph
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Title not available (Why is that?)
• Finding a Maximum Clique in an Arbitrary Graph
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• An exact algorithm for the maximum clique problem
• Finding maximum cliques in arbitrary and in special graphs
• 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
• A branch and bound algorithm for the maximum clique problem
• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring

Cited In (23)

• On the minimum number of logical clauses inferred from examples
• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• Estimating clique size by coloring the nodes of auxiliary graphs
• Solving the minimum-weighted coloring problem
• The maximum clique problem
• An exact algorithm for the maximum probabilistic clique problem
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Detecting robust cliques in graphs subject to uncertain edge failures
• A fast algorithm for the maximum clique problem
• Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem
• New lower bounds on the weighted chromatic number of a graph
• Reducing graph coloring to clique search
• Title not available (Why is that?)
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Efficient pattern matching on big uncertain graphs
• Infra-chromatic bound for exact maximum clique search
• Solving hard set covering problems
• Iterative coloring extension of a maximum clique
• An algorithm for finding a maximum clique in a graph
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• Co-2-plex vertex partitions
• A note on fractional coloring and the integrality gap of LP for maximum weight independent set

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1913697)