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

Mathieu Bouchard (), Alain Hertz () and Guy Desaulniers ()
Additional contact information
Mathieu Bouchard: École Polytechnique de Montréal and GERAD
Alain Hertz: École Polytechnique de Montréal and GERAD
Guy Desaulniers: École Polytechnique de Montréal and GERAD

Journal of Combinatorial Optimization, 2009, vol. 17, issue 2, No 4, 168-191

Abstract: Abstract An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D v (G,c) the minimum number of integers which must be added to S v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ v∈V D v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.

Keywords: Edge coloring; Minimum deficiency problem; Tabu search (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9106-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:17:y:2009:i:2:d:10.1007_s10878-007-9106-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9106-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().