On local search for the generalized graph coloring problem

On local search for the generalized graph coloring problem

0.00 Avg rating0 Votes
Article ID: iaor2004359
Country: Netherlands
Volume: 31
Issue: 1
Start Page Number: 28
End Page Number: 34
Publication Date: Jan 2003
Journal: Operations Research Letters
Authors: ,
Keywords: graph colouring
Abstract:

Given an edge-weighted graph and an integer k, the generalized graph coloring problem is the problem of partitioning the vertex set into k subsets so as to minimize the total weight of the edges that are included in a single subset. We recall a result on the equivalence between Karush–Kuhn–Tucker points for a quadratic programming formulation and local optima for the simple flip-neighborhood. We also show that the quality of local optima with respect to a large class of neighborhoods may be arbitrarily bad and that some local optima may be hard to find.

Reviews

Required fields are marked *. Your email address will not be published.