Search results for "Graph theory"

Principles of scatter search

2006

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems. This paper provides…

Real-Time Routing Selection in Flexible Manufacturing Systems

1993

Routing flexibility is one of the main peculiarities of Flexible Manufacturing Systems. This paper proposes three methods for real-time routing selection. The first one makes decisions comparing the current workload of machines in each alternative path. The second method considers the current workloads at the bottleneck machines in each allowed route. The third approach makes real-time decisions minimizing a merit index that represents a measure of the still required resource amount. The index is computed by short discrete-event simulation runs. Some case studies evaluate and compare the proposed approaches.

Converging paths to Notes

1995

The nature of the information systems needed in a networked firm is not well known: nor is the process leading to particular solutions. Describes a small computer‐consulting company which works as a network of independent consultants, and analyses the slow and circuitous path from recognizing its IS/IT needs to its commitment to a particular solution as seven steps; using ideas of structuration theory as a focus. During the selection process, participants formed new interpretations of the firm, of technology, and of the appropriate process towards a feasible solution. New resources – both material and symbolic – were acquired to enable the search. Existing “norms” provided boundaries for th…

Social Network Analysis of Sicilian Mafia Interconnections

2019

In this paper, we focus on the study of Sicilian Mafia organizations through Social Network Analysis. We analyse datasets reflecting two different Mafia Families, based on examinations of digital trails and judicial documents, respectively. The first dataset includes the phone calls logs among suspected individuals. The second one is based on police traces of meeting that have taken place among different types of criminals. Our breakthrough is twofold. First in the method followed to generate these new datasets. Second, in the method used to carry out a quantitative phenomena investigation that are hard to evaluate. Our networks are weighted ones, with each weight catching the frequency of …

Table of Periodic Properties of Fullerenes Based on Structural Parameters.

2004

The periodic table (PT) of the elements suggests that hydrogen could be the origin of everything else. The construction principle is an evolutionary process that is formally similar to those of Darwin and Oparin. The Kekulé structure count and permanence of the adjacency matrix of fullerenes are related to structural parameters involving the presence of contiguous pentagons p, q and r. Let p be the number of edges common to two pentagons, q the number of vertices common to three pentagons, and r the number of pairs of nonadjacent pentagon edges shared between two other pentagons. Principal component analysis (PCA) of the structural parameters and cluster analysis (CA) of the fullerenes perm…

Quantitative lower bounds to the Euclidean and the Gaussian Cheeger constants

2020

We provide a quantitative lower bound to the Cheeger constant of a set $\Omega$ in both the Euclidean and the Gaussian settings in terms of suitable asymmetry indexes. We provide examples which show that these quantitative estimates are sharp.

Special issue of Computers and Operations Research: GRASP with Path Relinking: Developments and applications

2013

The pruning-grafting lattice of binary trees

2008

AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.

On the exhaustive generation of k-convex polyominoes

2017

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper we present a simple algorithm for computing the degree of convexity of a convex polyomino and we show how it can be used to design an algorithm that generates, given an integer k, all k-convex polyominoes of area n in constant amortized time, using space O(n). Furthermore, by applying few changes, we are able to generate all convex polyominoes whose degree of convexity is exactly k.

Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes

2006

A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…