Lower bounds and a tabu search algorithm for the minimum deficiency problem

DOI10.1007/S10878-007-9106-0MaRDI QIDQ841600zbMATH OpenOpenAlexFDO

Authors Mathieu Bouchard, Alain Hertz, Guy Desaulniers

Publication date 18 September 2009

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-007-9106-0

zbMATH Keywords

edge coloringminimum deficiency problemtabu search

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Further results on the deficiency of graphs
• A comparison of integer and constraint programming models for the deficiency problem
• Integer programming formulations for minimum deficiency interval coloring
• The deficiency of a regular graph
• Cyclic deficiency of graphs

Cites work

• Consecutive colorings of the edges of general graphs
• Generating random regular graphs
• scientific article; zbMATH DE number 951847 (Why is no real title available?)
• scientific article; zbMATH DE number 1409249 (Why is no real title available?)
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• 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

(9)

• Cyclic deficiency of graphs
• Further results on the deficiency of graphs
• Symmetry breaking constraints for the minimum deficiency problem
• A comparison of integer and constraint programming models for the deficiency problem
• Integer programming formulations for minimum deficiency interval coloring
• On resistance of graphs
• On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic
• On deficiency of complete 3-partite and 4-partite graphs
• Interval edge-colorings of complete graphs and \(n\)-dimensional cubes

Describes a project that uses

Uses Software

• Tabu search

This page was built for publication: Lower bounds and a tabu search algorithm for the minimum deficiency problem

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