A simple branching scheme for vertex coloring problems

We present a branching scheme for some vertex coloring problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme.     

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

We study graph multicoloring problems, motivated by the scheduling of dependent jobs on multiple machines. In multicoloring problems, vertices have lengths which determine the number of colors they must receive, and the desired coloring can be either contiguous (nonpreemptive schedule) or arbitrary (preemptive schedule). We consider both the sum-of-completion times measure, or the sum of the last color assigned to each vertex, as well as the more common makespan measure, or the number of colors used. In this paper, we study two fundamental classes of graphs: planar graphs and partial k-trees. For both classes, we give a polynomial time approximation scheme (PTAS) for the multicoloring sum, for both the preemptive and nonpreemptive cases. On the other hand, we show the problem to be strongly NP-hard on planar graphs, even in the unweighted case, known as the sum coloring problem. For a nonpreemptive multicoloring sum of partial k-trees, we obtain a fully polynomial time approximation scheme. This is based on a pseudo-polynomial time algorithm that holds for a general class of cost functions. Finally, we give a PTAS for the makespan of a preemptive multicoloring of partial k-trees that uses only O(log n) preemptions. These results are based on several properties of multicolorings and tools for manipulating them, which may be of more general applicability.     

On a generalization of the Gallai-Roy-Vitaver theorem to the bandwidth coloring problem

We generalize to the bandwidth coloring problem a classical theorem, discovered independently by Gallai, Roy and Vitaver, in the context of the graph coloring problem. Two proofs are given, a simple one and a more complex one that is based on a series of equivalent mathematical programming models.     

An improved simulated annealing algorithm for bandwidth minimization

In this paper, a simulated annealing algorithm is presented for the bandwidth minimization problem for graphs. This algorithm is based on three distinguished features including an original internal representation of solutions, a highly discriminating evaluation function and an effective neighborhood. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of some previous best results.     

Sum Multicoloring of Graphs

Scheduling dependent jobs on multiple machines is modeled by the graph multicoloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multicoloring problem: Given a graph and the number of colors required by each vertex, find a multicoloring which minimizes the sum of the largest colors assigned to the vertices. It reduces to the known sum coloring problem when each vertex requires exactly one color.This paper reports a comprehensive study of the sum multicoloring problem, treating three models: with and without preemptions, as well as co-scheduling where jobs cannot start while others are running. We establish a linear relation between the approximability of the maximum independent set problem and the approximability of the sum multicoloring problem in all three models, via a link to the sum coloring problem. Thus, for classes of graphs for which the independent set problem is ρ-approximable, we obtain O(ρ)-approximations for preemptive and co-scheduling sum multicoloring and O(ρ log n)-approximation for nonpreemptive sum multicoloring. In addition, we give constant ratio approximations for a number of fundamental classes of graphs, including bipartite, line, bounded degree, and planar graphs.     

Extending the disjoint‐representatives theorems of Hall,Halmos, and Vaughan to list‐multicolorings of graphs

Philip Hall's famous theorem on systems of distinct representatives and its not‐so‐famous improvement by Halmos and Vaughan (1950) can be regarded as statements about the existence of proper list‐colorings or list‐multicolorings of complete graphs. The necessary and sufficient condition for a proper “coloring” in these theorems has a rather natural generalization to a condition we call Hall's condition on a simple graph G, a vertex list assignment to G, and an assignment of nonnegative integers to the vertices of G. Hall's condition turns out to be necessary for the existence of a proper multicoloring of G under these assignments. The Hall‐Halmos‐Vaughan theorem may be stated: when G is a clique, Hall's condition is sufficient for the existence of a proper multicoloring. In this article, we undertake the study of the class HHV of simple graphs G for which Hall's condition is sufficient for the existence of a proper multicoloring. It is shown that HHV is contained in the class ℋ︁₀ of graphs in which every block is a clique and each cut‐vertex lies in exactly two blocks. On the other hand, besides cliques, the only connected graphs we know to be in HHV are (i) any two cliques joined at a cut‐vertex, (ii) paths, and (iii) the two connected graphs of order 5 in ℋ︁₀, which are neither cliques, paths, nor two cliques stuck together. In case (ii), we address the constructive aspect, the problem of deciding if there is a proper coloring and, if there is, of finding one. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 199–219, 2000     

A New Ant Colony Optimization Algorithm for the Lower Bound of Sum Coloring Problem

We consider an undirected graph G?=?(V, E), the minimum sum coloring problem (MSCP) asks to find a valid vertex coloring of G, using natural numbers (1,2,...), the aim is to minimize the total sum of colors. In this paper we are interested in the elaboration of an approximate solution for the minimum sum coloring problem (MSCP), more exactly we try to give a lower bound for MSCP by looking for a decomposition of the graph based on the metaheuristic of ant colony optimization (ACO). We test different instances to validate our approach.     

Constraint Propagation in Graph Coloring

In this paper we propose a method for integrating constraint propagation algorithms into an optimization procedure for vertex coloring with the goal of finding improved lower bounds. The key point we address is how to get instances of Constraint Satisfaction Problems (CSPs) from a graph coloring problem in order to give rise to new lower bounds outperforming the maximum clique bound. More precisely, the algorithms presented have the common goal of finding CSPs in the graph for which infeasibility can be proven. This is achieved by means of constraint propagation techniques which allow the algorithms to eliminate inconsistencies in the CSPs by updating domains dynamically and rendering such infeasibilities explicit. At the end of this process we use the largest CSP for which it has not been possible to prove infeasibility as an input for an algorithm which enlarges such CSP to get a feasible coloring. We experimented with a set of middle-high density graphs with quite a large difference between the maximum clique and the chromatic number.     

A fast algorithm for the maximum clique problem

Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. A branch-and-bound algorithm for the maximum clique problem—which is computationally equivalent to the maximum independent (stable) set problem—is presented with the vertex order taken from a coloring of the vertices and with a new pruning strategy. The algorithm performs successfully for many instances when applied to random graphs and DIMACS benchmark graphs.     

求解图着色问题的量子蚁群算法

针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.     

Variable neighbourhood search for bandwidth reduction

The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.     

Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.     

Reducing the bandwidth of a sparse matrix with a genetic algorithm

Abstract

The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.     

A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem

Vertex coloring problem is a combinatorial optimization problem in graph theory in which a color is assigned to each vertex of graph such that no two adjacent vertices have the same color. In this paper a new hybrid algorithm which is obtained from combination of cellular learning automata (CLA) and memetic algorithm (MA) is proposed for solving the vertex coloring problem. CLA is an effective probabilistic learning model combining cellular automata and learning automaton (LA). Irregular CLA (ICLA) is a generalization of CLA in which the restriction of rectangular grid structure in CLA is removed. The proposed algorithm is based on the irregular open CLA (IOCLA) that is an extension of ICLA in which the evolution of CLA is influenced by both local and global environments. Similar to other IOCLA-based algorithms, in the proposed algorithm, local environment is constituted by neighboring LAs of any cell and the global environment consists of a pool of memes in which each meme corresponds to a certain local search method. Each meme is represented by a set of LAs from which the history of the corresponding local search method can be extracted. To show the superiority of the proposed algorithm over some well-known algorithms, several computer experiments have been conducted. The results show that the proposed algorithm performs better than other methods in terms of running time of algorithm and the required number of colors.     

Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm

We present an exact algorithm for solving the generalized minimum spanning tree problem (GMST). Given an undirected connected graph and a partition of the graph vertices, this problem requires finding a least-cost subgraph spanning at least one vertex out of every subset. In this paper, the GMST is formulated as a minimum spanning tree problem with side constraints and solved exactly by a branch-and-bound algorithm. Lower bounds are derived by relaxing, in a Lagrangian fashion, complicating constraints to yield a modified minimum cost spanning tree problem. An efficient preprocessing algorithm is implemented to reduce the size of the problem. Computational tests on a large set of randomly generated instances with as many as 250 vertices, 1000 edges, and 25 subsets provide evidence that the proposed solution approach is very effective.     

A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

关于带宽极值问题的一些结果

本文研究的问题是确定f(p,B）的值，也就是给定顶点数p和带宽B，求满足最大度不超过B的连通图的最小边数，本文给出了一些f(p,B）的值及相应极图。     

Maximum-weight stable sets and safe lower bounds for graph coloring

The best method known for determining lower bounds on the vertex coloring number of a graph is the linear-programming column-generation technique, where variables correspond to stable sets, first employed by Mehrotra and Trick in 1996. We present an implementation of the method that provides numerically-safe results, independent of the floating-point accuracy of linear-programming software. Our work includes an improved branch-and-bound algorithm for maximum-weight stable sets and a parallel branch-and-price framework for graph coloring. Computational results are presented on a collection of standard test instances, including the unsolved challenge problems created by David S. Johnson in 1989.     

关于带宽极值问题的两个结果

本文研究的问题是确定ｅ＊（ｐ,Ｂ）的值,也就是确定顶点数为ｐ、带宽为Ｂ的连通图Ｇ的最小边数,本文给出当Ｂ＝ｐ＋３／２和Ｂ＝ｐ／２＋２时的精确结果。