Another look at graph coloring via propositional satisfiability

DOI10.1016/J.DAM.2006.07.016zbMath1131.05090OpenAlexW2030455524MaRDI QIDQ2467359

Allen van Gelder

Publication date: 21 January 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.016

zbMATH Keywords

graph coloringsymmetry breakingconstraint satisfactionpropositional satisfiabilityindependent-set analysis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

ASlib: a benchmark library for algorithm selection ⋮ Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming ⋮ A Boolean satisfiability approach to the resource-constrained project scheduling problem ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ Generalised graph colouring by a hybrid of local search and constraint programming ⋮ Coloring graphs by iterated local search traversing feasible and infeasible solutions ⋮ Graph coloring in the estimation of sparse derivative matrices: Instances and applications ⋮ Embedding a novel objective function in a two-phased local search for robust vertex coloring ⋮ A NEW APPROACH TO THE VERTEX COLORING PROBLEM ⋮ Dynamic Symmetry Breaking by Simulating Zykov Contraction ⋮ CsegGraph: a graph colouring instance generator ⋮ meSAT: multiple encodings of CSP to SAT ⋮ Optimal direct determination of sparse Jacobian matrices

Uses Software

• SATO
• Chaff
• DIMACS
• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• An extension to linear resolution with selection function
• An efficient algorithm for the 3-satisfiability problem
• Controlled integration of the cut rule into connection tableau calculi
• Autarky pruning in propositional model elimination reduces failure redundancy
• Graph coloring in the estimation of sparse derivative matrices: Instances and applications
• A graph coloring algorithm for large scheduling problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• GRASP: a search algorithm for propositional satisfiability
• SATO: An efficient propositional prover
• A Simplified Format for the Model Elimination Theorem-Proving Procedure
• A machine program for theorem-proving
• Frozen development in graph coloring

This page was built for publication: Another look at graph coloring via propositional satisfiability