Another look at graph coloring via propositional satisfiability
DOI10.1016/J.DAM.2006.07.016zbMATH Open1131.05090OpenAlexW2030455524MaRDI QIDQ2467359FDOQ2467359
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
Recommendations
constraint satisfactiongraph coloringsymmetry breakingpropositional satisfiabilityindependent-set analysis
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)
Cites Work
- Frozen development in graph coloring
- 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
- A machine program for theorem-proving
- SATO: An efficient propositional prover
- A Simplified Format for the Model Elimination Theorem-Proving Procedure
- Title not available (Why is that?)
- Using tabu search techniques for graph coloring
- Title not available (Why is that?)
- Autarky pruning in propositional model elimination reduces failure redundancy
- An efficient algorithm for the 3-satisfiability problem
- Title not available (Why is that?)
- Controlled integration of the cut rule into connection tableau calculi
- Title not available (Why is that?)
- An extension to linear resolution with selection function
- Graph coloring in the estimation of sparse derivative matrices: Instances and applications
Cited In (18)
- 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
- A NEW APPROACH TO THE VERTEX COLORING PROBLEM
- aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming
- Theory and Applications of Satisfiability Testing
- ASlib: a benchmark library for algorithm selection
- CsegGraph: a graph colouring instance generator
- Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization
- Better test results for the graph coloring and the pigeonhole problems using DPLL with \(k\)-literal representation
- Title not available (Why is that?)
- Constraint and Satisfiability Reasoning for Graph Coloring
- 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
- Graph coloring in the estimation of sparse derivative matrices: Instances and applications
- Optimal direct determination of sparse Jacobian matrices
- Constraint propagation in graph coloring
Uses Software
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)
