Constraint and satisfiability reasoning for graph coloring
DOI10.1613/JAIR.1.11313zbMATH Open1490.68205OpenAlexW3083503609MaRDI QIDQ5129999FDOQ5129999
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
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Reducibility among combinatorial problems
- On the Shannon capacity of a graph
- Sur le coloriage des graphs
- The ellipsoid method and its consequences in combinatorial optimization
- k-Degenerate Graphs
- The complexity of theorem-proving procedures
- Title not available (Why is that?)
- A new \textsf{DSATUR}-based algorithm for exact vertex coloring
- Another look at graph coloring via propositional satisfiability
- A survey on vertex coloring problems
- New methods to color the vertices of a graph
- An exact approach for the vertex coloring problem
- GRASP: a search algorithm for propositional satisfiability
- Worst-case Analysis of Set Union Algorithms
- A Column Generation Approach for Graph Coloring
- Lazy model expansion: interleaving grounding with search
- A one-to-one correspondence between colorings and stable sets
- Lower bounding techniques for DSATUR-based branch and bound
- Models and solution techniques for frequency assignment problems
- An exact algorithm with learning for the graph coloring problem
- Title not available (Why is that?)
- Solving the maximum clique and vertex coloring problems on very large sparse networks
- APPLICATION OF THE GRAPH COLORING ALGORITHM TO THE FREQUENCY ASSIGNMENT PROBLEM
- Propagation = Lazy Clause Generation
- Optimal data reduction for graph coloring using low-degree polynomials
- Listing all maximal cliques in large sparse real-world graphs
- Dynamic Symmetry Breaking by Simulating Zykov Contraction
Cited In (7)
- Generalised graph colouring by a hybrid of local search and constraint programming
- Exact solution of graph coloring problems via constraint programming and column generation
- Title not available (Why is that?)
- Total coloring and total matching: polyhedra and facets
- Another look at graph coloring via propositional satisfiability
- Coloring terms to control equational reasoning
- Constraint propagation in graph coloring
Uses Software
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)
