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

DOI10.1007/s10878-007-9106-0zbMath1180.90344OpenAlexW1977507713MaRDI QIDQ841600

Guy Desaulniers, Alain Hertz, Mathieu Bouchard

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

tabu searchedge coloringminimum deficiency problem

Mathematics Subject Classification ID

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

Related Items (7)

Further results on the deficiency of graphs ⋮ A comparison of integer and constraint programming models for the deficiency problem ⋮ Symmetry Breaking Constraints for the Minimum Deficiency Problem ⋮ On resistance of graphs ⋮ On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic ⋮ Interval edge-colorings of complete graphs and \(n\)-dimensional cubes ⋮ Cyclic deficiency of graphs

Uses Software

• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On interval edge colorings of \((\alpha ,\beta )\)-biregular bipartite graphs
• On the deficiency of bipartite graphs
• The deficiency of a regular graph
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• Generating random regular graphs
• Consecutive colorings of the edges of general graphs

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