A comparison of integer and constraint programming models for the deficiency problem

DOI10.1016/J.COR.2015.10.016MaRDI QIDQ342299zbMATH OpenOpenAlexFDO

Authors Sivan Altinakar, Gilles Caporossi, Alain Hertz

Publication date 17 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2015.10.016

zbMATH Keywords

constraint programminginteger linear programmingcompact edge-colorings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Symmetry breaking constraints for the minimum deficiency problem
• Integer programming formulations for minimum deficiency interval coloring
• Lower bounds and a tabu search algorithm for the minimum deficiency problem
• Further results on the deficiency of graphs
• Cyclic deficiency of graphs

Cites work

• scientific article; zbMATH DE number 165470 (Why is no real title available?)
• scientific article; zbMATH DE number 951847 (Why is no real title available?)
• scientific article; zbMATH DE number 1409249 (Why is no real title available?)
• Compact Scheduling In Open Shop With Zero-One Time Operations
• Consecutive colorings of the edges of general graphs
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• Investigation on interval edge-colorings of graphs
• Lower bounds and a tabu search algorithm for the minimum deficiency problem
• On interval colourings of bi-regular bipartite graphs
• On interval edge colorings of ( , )-biregular bipartite graphs
• On the deficiency of bipartite graphs
• The deficiency of a regular graph

Cited in

(8)

• Integer programming models for the routing and spectrum allocation problem
• Symmetry breaking constraints for the minimum deficiency problem
• Cyclic deficiency of graphs
• Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs
• Integer programming formulations for minimum deficiency interval coloring
• Compact cyclic edge-colorings of graphs
• Lower bounds and a tabu search algorithm for the minimum deficiency problem
• Further results on the deficiency of graphs

Describes a project that uses

Uses Software

• Traces
• nauty

This page was built for publication: A comparison of integer and constraint programming models for the deficiency problem

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