Random graph coloring:Statistical physics approach

The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the two-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges. ©2002 The American Physical Society.

Coloring random graphs and maximizing local diversity

We study a variation of the graph coloring problem on random graphs of finite average connectivity. Given the number of colors, we aim to maximize the number of different colors at neighboring vertices (i.e. one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem.

A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems

This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach.

A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

Examination timetabling automation using hybrid meta-heuristics

Trabalho de projeto realizado para obtenção do grau de Mestre em Engenharia Informática e de Computadores

Modelagem matemática e aplicações do problema de coloração em grafos

Pós-graduação em Matemática - IBILCE

Estratégia de projeto de atribuição de comprimento de onda com restrição de camada física em redes WDM

O sistema WDM (Wavelength Division Multiplexing) é considerado como uma tecnologia madura para ser usada no backbone de redes ópticas. Entretanto, encontrar uma solução ótima para o algoritmo de atribuição de comprimento de onda no projeto e operação destas redes, ainda é uma questão em aberto. A pesquisa realizada nesta tese aborda os principais aspectos relacionados ao processo de atribuição de comprimento de onda em sistemas WDM, e como resultado foi proposta uma metodologia que minimiza a degradação do sinal óptico gerada pela modulação de fase cruzada (XPM – Cross-Phase Modulation). Esta proposta é composta por uma metodologia híbrida baseada em Coloração de Grafo e Algoritmo Genético (AG), sendo que o primeiro tem a função de reduzir o número de comprimentos de onda necessários para atender a matriz de tráfego (que é fornecida a priori) e o último tem a função de encontrar a ordem de ativação de canais na grade de comprimentos de onda, com o objetivo de reduzir o efeito XPM. A proposta foi comparada com o algoritmo First-Fit em diferentes cenários e topologias de redes, e demonstrou uma considerável redução na probabilidade de bloqueio.

Wavelength assignment using a hybrid evolutionary computation to reduce cross-phase modulation

In this paper, we propose a hybrid methodology based on Graph-Coloring and Genetic Algorithm (GA) to solve the Wavelength Assignment (WA) problem in optical networks, impaired by physical layer effects. Our proposal was developed for a static scenario where the physical topology and traffic matrix are known a priori. First, we used fixed shortest-path routing to attend demand requests over the physical topology and the graph-coloring algorithm to minimize the number of necessary wavelengths. Then, we applied the genetic algorithm to solve WA. The GA finds the wavelength activation order on the wavelengths grid with the aim of reducing the Cross-Phase Modulation (XPM) effect; the variance due to the XPM was used as a function of fitness to evaluate the feasibility of the selected WA solution. Its performance is compared with the First-Fit algorithm in two different scenarios, and has shown a reduction in blocking probability up to 37.14% when considered both XPM and residual dispersion effects and up to 71.42% when only considered XPM effect. Moreover, it was possible to reduce by 57.14% the number of wavelengths.

Uma proposta de oficina de coloração de mapas e grafos para o ensino fundamental e médio

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Performance evaluation of a parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes

[EN]A new parallel algorithm for simultaneous untangling and smoothing of tetrahedral meshes is proposed in this paper. We provide a detailed analysis of its performance on shared-memory many-core computer architectures. This performance analysis includes the evaluation of execution time, parallel scalability, load balancing, and parallelism bottlenecks. Additionally, we compare the impact of three previously published graph coloring procedures on the performance of our parallel algorithm. We use six benchmark meshes with a wide range of sizes. Using these experimental data sets, we describe the behavior of the parallel algorithm for different data sizes. We demonstrate that this algorithm is highly scalable when it runs on two different high-performance many-core computers with up to 128 processors...

Tutte's 5-flow conjecture

The aim of this thesis is to show and put together the results, obtained so far, useful to tackle a conjecture of graph theory proposed in 1954 by William Thomas Tutte. The conjecture in question is Tutte's 5-flow conjecture, which states that every bridgeless graph admits a nowhere-zero 5-flow, namely a flow with non-zero integer values between -4 and 4. We will start by giving some basics on graph theory, useful for the followings, and proving some results about flows on oriented graphs and in particular about the flow polynomial. Next we will treat two cases: graphs embeddable in the plane $\mathbb{R}^2$ and graphs embeddable in the projective plane $\mathbb{P}^2$. In the first case we will see the correlation between flows and colorings and prove a theorem even stronger than Tutte's conjecture, using the 4-color theorem. In the second case we will see how in 1984 Richard Steinberg used Fleischner's Splitting Lemma to show that there can be no minimal counterexample of the conjecture in the case of graphs in the projective plane. In the fourth chapter we will look at the theorems of François Jaeger (1976) and Paul D. Seymour (1981). The former proved that every bridgeless graph admits a nowhere-zero 8-flow, the latter managed to go even further showing that every bridgeless graph admits a nowhere-zero 6-flow. In the fifth and final chapter there will be a short introduction to the Tutte polynomial and it will be shown how it is related to the flow polynomial via the Recipe Theorem. Finally we will see some applications of flows through the study of networks and their properties.

Edge coloring BIBDS and constructing MOELRs

Chapter 1 is used to introduce the basic tools and mechanics used within this thesis. Some historical uses and background are touched upon as well. The majority of the definitions are contained within this chapter as well. In Chapter 2 we consider the question whether one can decompose λ copies of monochromatic Kv into copies of Kk such that each copy of the Kk contains at most one edge from each Kv. This is called a proper edge coloring (Hurd, Sarvate, [29]). The majority of the content in this section is a wide variety of examples to explain the constructions used in Chapters 3 and 4. In Chapters 3 and 4 we investigate how to properly color BIBD(v, k, λ) for k = 4, and 5. Not only will there be direct constructions of relatively small BIBDs, we also prove some generalized constructions used within. In Chapter 5 we talk about an alternate solution to Chapters 3 and 4. A purely graph theoretical solution using matchings, augmenting paths, and theorems about the edgechromatic number is used to develop a theorem that than covers all possible cases. We also discuss how this method performed compared to the methods in Chapters 3 and 4. In Chapter 6, we switch topics to Latin rectangles that have the same number of symbols and an equivalent sized matrix to Latin squares. Suppose ab = n2. We define an equitable Latin rectangle as an a × b matrix on a set of n symbols where each symbol appears either [b/n] or [b/n] times in each row of the matrix and either [a/n] or [a/n] times in each column of the matrix. Two equitable Latin rectangles are orthogonal in the usual way. Denote a set of ka × b mutually orthogonal equitable Latin rectangles as a k–MOELR(a, b; n). We show that there exists a k–MOELR(a, b; n) for all a, b, n where k is at least 3 with some exceptions.

Galerkin finite element method for incompressible thermofluid flows framed within the bond graph theory

In this paper a bond graph methodology is used to model incompressible fluid flows with viscous and thermal effects. The distinctive characteristic of these flows is the role of pressure, which does not behave as a state variable but as a function that must act in such a way that the resulting velocity field has divergence zero. Velocity and entropy per unit volume are used as independent variables for a single-phase, single-component flow. Time-dependent nodal values and interpolation functions are introduced to represent the flow field, from which nodal vectors of velocity and entropy are defined as state variables. The system for momentum and continuity equations is coincident with the one obtained by using the Galerkin method for the weak formulation of the problem in finite elements. The integral incompressibility constraint is derived based on the integral conservation of mechanical energy. The weak formulation for thermal energy equation is modeled with true bond graph elements in terms of nodal vectors of temperature and entropy rates, resulting a Petrov-Galerkin method. The resulting bond graph shows the coupling between mechanical and thermal energy domains through the viscous dissipation term. All kind of boundary conditions are handled consistently and can be represented as generalized effort or flow sources. A procedure for causality assignment is derived for the resulting graph, satisfying the Second principle of Thermodynamics. (C) 2007 Elsevier B.V. All rights reserved.

Optimization and Complexity Reduction of Switch-Reconfigured Antennas Using Graph Models

This letter addresses the optimization and complexity reduction of switch-reconfigured antennas. A new optimization technique based on graph models is investigated. This technique is used to minimize the redundancy in a reconfigurable antenna structure and reduce its complexity. A graph modeling rule for switch-reconfigured antennas is proposed, and examples are presented.