Generalised graph colouring by a hybrid of local search and constraint programming
DOI10.1016/J.DAM.2006.07.011zbMATH Open1179.90312OpenAlexW2070048232MaRDI QIDQ2467347FDOQ2467347
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.011
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) Nonlinear programming (90C30) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Negative effects of modeling techniques on search performance
- Another look at graph coloring via propositional satisfiability
- New methods to color the vertices of a graph
- A machine program for theorem-proving
- A Column Generation Approach for Graph Coloring
- Coloration neighbourhood search with forward checking
- Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
- On the parallel complexity of discrete relaxation in constraint satisfaction networks
- Combining the scalability of local search with the pruning techniques of systematic search
- Theory and Applications of Satisfiability Testing
- Incomplete dynamic backtracking for linear pseudo-Boolean problems
- Symmetry Breaking and Local Search Spaces
Cited In (12)
- Coloring graphs by iterated local search traversing feasible and infeasible solutions
- Exact solution of graph coloring problems via constraint programming and column generation
- A NEW APPROACH TO THE VERTEX COLORING PROBLEM
- CsegGraph: a graph colouring instance generator
- Polyhedral studies for minimum‐span graph labelling with integer distance constraints
- Graph coloring by multiagent fusion search
- Strong valid inequalities for Boolean logical pattern generation
- An exact algorithm with learning for the graph coloring problem
- A survey on vertex coloring problems
- Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model
- Hybrid metaheuristics for stochastic constraint programming
- An evolutionary approach for bandwidth multicoloring problems
Uses Software
Recommendations
- A survey of local search methods for graph coloring 👍 👎
- Graph colorings with local constraints -- a survey 👍 👎
- Exact solution of graph coloring problems via constraint programming and column generation 👍 👎
- Coloring graphs by iterated local search traversing feasible and infeasible solutions 👍 👎
- The complexity of generalized graph colorings 👍 👎
- On local search for the generalized graph coloring problem 👍 👎
- Constraint and Satisfiability Reasoning for Graph Coloring 👍 👎
- Efficient constraint propagation for graph coloring 👍 👎
- Local optimization of colorings of graphs 👍 👎
This page was built for publication: Generalised graph colouring by a hybrid of local search and constraint programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467347)
