Another look at graph coloring via propositional satisfiability

DOI10.1016/J.DAM.2006.07.016MaRDI QIDQ2467359zbMATH OpenOpenAlexFDO

Authors 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

constraint satisfactiongraph coloringsymmetry breakingpropositional satisfiabilityindependent-set analysis

Mathematics Subject Classification ID

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

Recommendations

• Constraint and satisfiability reasoning for graph coloring
• Theory and Applications of Satisfiability Testing
• Constraint propagation in graph coloring
• scientific article; zbMATH DE number 5305148
• A Pruning Procedure for Exact Graph Coloring

Cites work

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

Cited in

(18)

• Constraint and satisfiability reasoning for graph coloring
• Computation with polynomial equations and inequalities arising in combinatorial optimization
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Generalised graph colouring by a hybrid of local search and constraint programming
• meSAT: multiple encodings of CSP to SAT
• ASlib: a benchmark library for algorithm selection
• Theory and Applications of Satisfiability Testing
• CsegGraph: a graph colouring instance generator
• Better test results for the graph coloring and the pigeonhole problems using DPLL with \(k\)-literal representation
• scientific article; zbMATH DE number 5305148 (Why is no real title available?)
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• A Boolean satisfiability approach to the resource-constrained project scheduling problem
• Dynamic Symmetry Breaking by Simulating Zykov Contraction
• aspartame: solving constraint satisfaction problems with answer set programming
• Graph coloring in the estimation of sparse derivative matrices: Instances and applications
• Optimal direct determination of sparse Jacobian matrices
• A new approach to the vertex coloring problem
• Constraint propagation in graph coloring

Describes a project that uses

Uses Software

• DIMACS
• Chaff
• SATO
• CsegGraph

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

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