Constraint and satisfiability reasoning for graph coloring

DOI10.1613/JAIR.1.11313MaRDI QIDQ5129999zbMATH OpenOpenAlexFDO

Authors Emmanuel Hebrard, George Katsirelos

Publication date 3 November 2020

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.1.11313

zbMATH Keywords

constraint programmingsatisfiability

Mathematics Subject Classification ID

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

Recommendations

• Another look at graph coloring via propositional satisfiability
• Constraint propagation in graph coloring
• Dynamic Symmetry Breaking by Simulating Zykov Contraction
• A Pruning Procedure for Exact Graph Coloring
• Lower bounding techniques for DSATUR-based branch and bound

Cites work

• k-Degenerate Graphs
• A Column Generation Approach for Graph Coloring
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• A one-to-one correspondence between colorings and stable sets
• A survey on vertex coloring problems
• An exact algorithm with learning for the graph coloring problem
• An exact approach for the vertex coloring problem
• Another look at graph coloring via propositional satisfiability
• APPLICATION OF THE GRAPH COLORING ALGORITHM TO THE FREQUENCY ASSIGNMENT PROBLEM
• Dynamic Symmetry Breaking by Simulating Zykov Contraction
• GRASP: a search algorithm for propositional satisfiability
• scientific article; zbMATH DE number 2080324 (Why is no real title available?)
• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• Lazy model expansion: interleaving grounding with search
• Listing all maximal cliques in large sparse real-world graphs
• Lower bounding techniques for DSATUR-based branch and bound
• Models and solution techniques for frequency assignment problems
• New methods to color the vertices of a graph
• On the Shannon capacity of a graph
• Optimal data reduction for graph coloring using low-degree polynomials
• Propagation = Lazy Clause Generation
• Reducibility among combinatorial problems
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• Sur le coloriage des graphs
• The complexity of theorem-proving procedures
• The ellipsoid method and its consequences in combinatorial optimization
• Worst-case Analysis of Set Union Algorithms

Cited in

(8)

• Coloring terms to control equational reasoning
• Generalised graph colouring by a hybrid of local search and constraint programming
• Another look at graph coloring via propositional satisfiability
• Total coloring and total matching: polyhedra and facets
• Exact solution of graph coloring problems via constraint programming and column generation
• scientific article; zbMATH DE number 5305148 (Why is no real title available?)
• Constraint propagation in graph coloring
• SAT encoding of partial ordering models for graph coloring problems

Describes a project that uses

Uses Software

• Chaff

This page was built for publication: Constraint and satisfiability reasoning for graph coloring

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