Efficient constraint propagation for graph coloring

DOI10.1016/J.ENDM.2011.05.042MaRDI QIDQ2840716zbMATH OpenOpenAlexFDO

Authors Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, Mouny Samy Modeliar

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2011.05.042

zbMATH Keywords

arc consistencyconstraint propagationgraph coloring

Mathematics Subject Classification ID

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

Recommendations

• Constraint propagation in graph coloring
• Using an incomplete version of dynamic backtracking for graph colouring
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Propagation rules for graph partitioning constraints

Cites work

• Collective dynamics of `small-world' networks
• Handbook of constraint programming.

Cited in

(7)

• Vertex coloring of a graph for memory constrained scenarios
• Generalised graph colouring by a hybrid of local search and constraint programming
• Using an incomplete version of dynamic backtracking for graph colouring
• Exact solution of graph coloring problems via constraint programming and column generation
• Lazy constraint imposing for improving the path constraint
• Propagation rules for graph partitioning constraints
• Constraint propagation in graph coloring

This page was built for publication: Efficient constraint propagation for graph coloring

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