Bandelt and Mulder’s structural characterization of bipartite distance hereditary graphs asserts that such graphs can be built inductively starting from a single vertex and by repeatedly adding either pendant vertices or twins (i.e., vertices with the same neighborhood as an existing one). Dirac and Duffin’s structural characterization of 2–connected series–parallel graphs asserts that such graphs can be built inductively starting from a single edge by adding either edges in series or in parallel. In this paper we give an elementary proof that the two constructions are the same construction when bipartite graphs are viewed as the fundamental graphs of a graphic matroid. We then apply the result to re-prove known results concerning bipartite distance hereditary graphs and series–parallel graphs and to provide a new class of polynomially-solvable instances for the integer multi-commodity flow of maximum value.

The role of information management and retrieval in production processes has been gaining in importance in recent years. In this context, the ability to search for and quickly find the small piece of information needed from the huge amount of information available has crucial importance. One category of tools devoted to such a task is represented by search engines. Satisfying the basic needs of the Web user has led to the research of new tools that aim at helping more sophisticated users (communities, companies, interest groups) with more elaborate methods. An example is the use of clustering and classification algorithms or other specific data mining techniques. In such a context, the proper use of a thematic search engine is a crucial tool in supporting and orienting many activities. Several prac- tical and theoretical problems arise in developing such tools, and we try to face some of these in this paper, extending previous work on Web mining. Here we consider two related problems: how to select an appropriate set of keywords for a thematic engine taking into account the semantic and linguistic extensions of the search context, and how to select and rank a subset of relevant pages given a set of search keywords. Both problems are solved using the same framework, based on a graph representation of the available information and on the search of particular node subsets of such a graph. Such subsets are effectively identified by a maximum-weight clique algorithm customized ad hoc for specific problems. The methods have been developed in the framework of a funded research project for the development of new Web search tools, they have been tested on real data, and are currently being implemented in a prototypal thematic search engine. The Web mining method presented in this paper can be applied to Web-based design and manufacturing.

Il questo lavoro viene presentato un algoritmo euristico basato su ricerca locale per graph coloring.

A new fast iterative algorithm is proposed to denoise images affected by Gaussian additive noise, by solving a constrained optimization problem. A family of functionals parameterized by a few hyperparameters already proposed in the literature to solve denoising problems is considered. The algorithm estimates jointly the image and the hyperparameters, therefore providing an automatic method. Each member of the family is made up of a coherence with the data term and a term enforcing a roughness penalty and preserving jump discontinuities. Assuming we know the noise variance, an adequacy constraint is also considered. The algorithm computes a member of the family and a minimizer of it which satisfies the constraint. A convergence proof is provided. We then consider a heuristic version of the algorithm which gives restorations of comparable quality whose computational complexity is a linear function of the pixels number. Experimental results on synthetic and real data are presented. Moreover, numerical comparisons with several fast denoising methods are provided.

The problem of obtaining relevant results in web searching has been tackled with several approaches. Although very e0ective techniques are currently used by the most popular search engines when no a priori knowledge on the user's desires beside the search keywords is available, in di0erent settings it is conceivable to design search methods that operate on a thematic database of web pages that refer to a common body of knowledge or to speci3c sets of users. We have considered such premises to design and develop a search method that deploys data mining and optimization techniques to provide a more signi3cant and restricted set of pages as the 3nal result of a user search. We adopt a vectorization method based on search context and user pro&le to apply clustering techniques that are then re3ned by a specially designed genetic algorithm. In this paper we describe the method, its implementation, the algorithms applied, and discuss some experiments that has been run on test sets of web pages.

Nel presente lavoro si studia lo scheduling nelle celle robotizzate in presenza di un braccio meccanico che deve eseguire operazioni di load, process e unload su macchine a controllo numerico. Viene studiata la complessità del problema quando l'obiettivo è la minimizzazione del tempo di completamento delle lavorazione relative ai pezzi nello shop. Per questo problema viene sviluppata un'euristica e se ne mostra il comportamento sperimentale.

Nel presente lavoro ci si occupa dello scheduling su griglie computazionali, fornendo un modello basato sul problema del rectangle packing. Viene fornita un'ampia sperimentazione, anche in presenza di malleabilità dei task da schedulare.

Questo lavoro si occupa di graph coloring. In particolare viene proposto un algoritmo di branch and bound troncato in grado di calcolare buoni lower bound sul numero cromatico di un grafo e spesso fornisce la soluzione ottima.

Nel presente lavoro studiamo problemi di localizzazione stocastica.

Il lavoro presenta dei lower bound sul numero cromatico di un grafo con pesi sui nodi.

In the field of resource constrained scheduling, the papers in the literature are mainly focused on minimizing the maximum completion time of a set of tasks to be carried out, paying attention to respecting the maximum simultaneous availability of each resource type in the system. This work, instead, considers the issues of balancing the resource usage and minimizing the peak of the resources allocated each time in the schedule, while keeping the makespan low. To this aim we propose a local search algorithm which acts as a multi start greedy heuristic. Extensive experiments on various randomly generated test instances are provided. Furthermore, we present a comparison with lower bounds and known heuristics.

In this paper an on-line algorithm for the Rectangle Packing Problem is presented. The method is designed to be able to accept or reject incoming boxes to maximize efficiency. We provide a wide computational analysis showing the behavior of the proposed algorithm as well as a comparison with existing off-line heuristics.

We study the on-line version of the well known problem of scheduling a set of $n$ independent multiprocessor tasks with prespecified processor allocations on a set of identical processors in order to minimize the makespan. Recently, it has been proven that even in the off-line case with unit processing time tasks no polynomial time approximation algorithm can be found with approximation factor $m^{{1}/{2}-\eps}$ for any $\eps >0$, unless \NP=\ZPP. We first study simple approximation and on-line algorithms based on the classical first-fit technique. Then, by using a split-round technique, we give a $3 \sqrt{m}$-approximation algorithm for the off-line version of the problem. Finally, we adapt this algorithm to the on-line case, in the paradigm of tasks arriving over time, and show that its competitive ratio is bounded by $(6\sqrt{m}+1)$. Due to the conducted experimental results, which also analyzed here, we conclude that our algorithms can also perform well in practice.