Search

Graph coloring is one of the hardest combinatorial optimization problems for which a wide variety of algorithms has been proposed over the last 30 years. The problem is as follows: given a graph one has to assign a label to each vertex such that no monochromatic edge appears and the number of different labels used is minimized. In this paper we present a new heuristic for this problem which works with two different functionalities. One is defined by two greedy subroutines, the former being a greedy constructive one and the other a greedy modification one. The other functionality is a perturbation subroutine, which can produce also infeasible colorings, and the ability is then to retrieve feasible solutions. In our experimentation the proper tuning of this optimization scheme produced good results on known graph coloring benchmarks.

In this work we give a new lower bound on the chromatic number of a Mycielski graph Mi. The result exploits a mapping between the coloring problem and a multiprocessor task scheduling problem. The tightness of the bound is proved for i=1,…,8.

A comparability graph is a graph which admits a transitive orientation. In this paper we consider the problem of augmenting a graph to a comparability graph in such a way that the maximum weight of its cliques is minimum. The problem is equivalent to a multiprocessor scheduling problem and to the interval coloring problem; and in the unweighted case also to the chromatic number problem. In the general case, the problem is NP-hard in the strong sense even on some very simple types of perfect graphs. We give complexity and approximation results for two subclasses of perfect graphs, namely for split graphs and stars of cliques, for which the problem still remains intractable but admits efficient estimations.

In this paper we present a novel coloring algorithm based on local search. We analyze its performance, and report several experimental results on DIMACS benchmark graphs. From our experiments, this algorithm looks robust, and yields a substantial speed up on previous algorithms for coloring. Our algorithm improves the best known coloring for four different DIMACS benchmark graphs: namely, Le450-25c, Le450-25d and Flat300_28_0 and Flat1000_76_0. Furthermore, we have run experiments on a simulator to get insights on its cache consciousness: from these experiments, it appears that the algorithm performs substantially less cache misses than other existing algorithms.

We consider the problem of evaluating the performance of a 5G network based on reusable components, called Reusable Functional Blocks (RFBs), proposed by the Horizon 2020 SUPERFLUIDITY project. RFBs allow a high level of flexibility, agility, portability and high performance. After formally modelling the RFB entities and the network physical nodes, we optimally formulate the problem of maximizing different Key Performance Indicators (KPIs) on an RFB-based network architecture, in which the RFBs are shared among the nodes, and deployed only where and when they are really needed. Our results, obtained by solving the proposed optimization problem over a simple yet representative scenario, show that the network can be managed in a very efficient way. More in depth, the RFBs are placed into the nodes in accordance with the amount of requested traffic from users and the specific pursued KPI, e.g., maximization of user throughput or minimization of the number of used nodes. Moreover, we evaluate the relationship between the capacity of each node and the number of RFBs deployed on it.

We consider the problem of scheduling no-wait jobs, with release dates and sequence dependent setup times, on a flow shop to minimize the makespan. We show that this problem is equivalent to the asymmetric traveling salesman problem with additional visiting time constraints. For this latter problem we give a mathematical formulation and two lower bounds. Two heuristic algorithms for solving the scheduling problem are proposed. Performance analysis of both lower bounds and heuristics on randomly generated test problems are carried out.