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

DOI10.1007/s10878-007-9106-0zbMath1180.90344MaRDI 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 search; edge coloring; minimum deficiency problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

05C15: Coloring of graphs and hypergraphs

Related Items

A comparison of integer and constraint programming models for the 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, Further results on the deficiency of graphs, Symmetry Breaking Constraints for the Minimum Deficiency Problem

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