  


Integer Programming Formulations for Minimum Deficiency Interval Coloring
Merve Bodur (merve.bodurgatech.edu) Abstract: A proper edgecoloring of a given undirected graph with natural numbers identified with colors is an interval (or consecutive) coloring if the colors of edges incident to each vertex form an interval of consecutive integers. Not all graphs admit such an edgecoloring and the problem of deciding whether a graph is interval colorable is NPcomplete. For a graph that is not interval colorable, determining a graph invariant called the (minimum) deficiency is a widely used approach. Deficiency is a measure of how close the graph is to have an interval coloring and can be described as the minimum number of pendant edges whose attachment makes the graph interval colorable. The majority of the studies in the literature either derive bounds on the deficiency of general graphs, or calculate the deficiency of graphs belonging to some special graph classes. In this work, we formulate the Minimum Deficiency Problem, to find the exact deficiency value for any given graph, as an integer program, and further enhance the formulation by introducing a family of valid inequalities. Then, we solve our model via a branchandcut algorithm. Our computational study on a large set of random graphs illustrates the strength of our formulation and the efficiency of the proposed approach. Keywords: Interval (consecutive) edgecoloring; minimum deficiency problem; integer programming; cutting planes; column generation Category 1: Integer Programming Category 2: Integer Programming (Cutting Plane Approaches ) Category 3: Combinatorial Optimization (Graphs and Matroids ) Citation: Download: [PDF] Entry Submitted: 07/21/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  