Sapienza University of Rome Computer Science Department

Algorithms and Data
Structures Group

Topics Network

Research

The Algorithms Group has interests and expertise in most active areas of current research within the design, analysis and applications of algorithms. Namely, its memebers conduct researches with particular emphasis on the following topics:

Algorithm Engineering
In recent years, many areas of theoretical computer science have shown growing interest in solving problems arising in real-world applications, experiencing a remarkable shift to more application-motivated research. However, for many decades, researchers have been mostly using mathematical methods (e.g., asymptotic analysis) for analyzing and predicting the behavior of algorithms. The new demand for algorithms that are of practical utility has now raised the need to refine and reinforce the traditional theoretical approach with experimental studies. In this context we study how the general models and techniques used by theoreticians can fit to actual existing machines: this implies to consider often overlooked, yet practically important issues such as hidden constant factors, effects of the memory hierarchy, implications of communication complexity, numerical precision, and use of heuristics.
Algorithms for Massive Data Sets
Many large-scale applications require the processing of massive data sets, which can easily reach the order of Terabytes. For instance, NASA's Earth Observing System generates Petabytes of data per year, while Google currently reports to be indexing and searching over 8 billion Web pages. In all such applications, there is an increasing demand for efficient algorithms able to deal with huge information structures. This represents a major challenge. In most cases, data are stored in external memory and new algorithmic techniques are needed in order to minimize disk accesses; in some cases data are so large that they cannot even fit in external memory but have to be analyzed 'on the fly'. In these scenarios, we study how algorithm design techniques and technological aspects of complex memory systems interact and adapt to each other.
Distributed Algorithms
We study basic combinatorial problems in a distributed setting, such as vertex and edge colorings. In recent work we succesfully extended the primal-dual schema to a distributed setting, applying it to basic scheduling and covering problems.
Graph Coloring Generalizations
One of the key topics in graph theory is graph coloring. Fascinating generalizations of the notion of graph coloring are motivated by problems of channel assignment in wireless communications, traffic phasing, fleet maintenance, task assignment, and other applications. While in the classical vertex coloring problem a condition is imposed only on colors of adjacent nodes, many generalizations require colors to respect a stronger condition, e.g. restrictions are imposed on colors both of adjacent nodes and of nodes at larger distance in the graph. We focus on some graph coloring generalizations that arose first from a channel assignment problem in radio networks, looking for exact and approximation efficient coloring algorithms on specific graph classes.
Graph Drawing
The visualization of complex conceptual structures is a key component of support tools for many applications. A graph is an abstract structure that is used to model information constituted by objects and connections between those objects. Hence, many information visualization systems require graphs to be drawn so that they are easy to read and understand. We design algorithms for authomatically generating clear and readable geometric representations of graphs, networks and related combinatorial structures.
Probabilistic Protocols for Networks
Probablistic networks are often the solution of choice for many network problems. In recent work we developed simple and very effective probabilistic protocols for computing backbones and overlays in ad-hoc, peer-to-peer and sensor networks.
Resilient Algorithms and Data Structures
Some of today's applications run on computer platforms with large and inexpensive memories, which are also error-prone: the content of a memory unit may be temporarily or permanently lost or damaged, depending on manufacturing defects, power failures, or environmental conditions. Faulty memories may cause a variety of problems in most software applications, since the appearance of even very few memory faults may jeopardize the correctness of the computational results. When specific hardware for fault detection and correction is not available or is too expensive, it makes sense to look for a solution to these problems at the application level. In this context, we are interested in the design of algorithms and data structures that are able to perform efficiently the tasks they were designed for, even in the presence of unreliable or corrupted information.
Tree Encoding
Coding trees by means of strings of vertex labels is a compact and interesting alternative to usual representations of trees; it also has many practical applications. Along the years several codes (combinatorial bijections between labeled trees and strings) have been introduced in the literature. We work on algorithmic aspects related to encoding, decoding, and properties of these codes. We are also interested in bijective codes for superclasses of trees like k-tree, partial k-tree, k-arch graphs.
Web Information Retrieval
We are interested in basic algorithmic issues that remain central to (web) information retrieval such as nearest neighbour algorithms, caching policies and optimization of basic data structures such as skips and skip lists. We are also investigating mathematical models for the web and other social networks that can faithfully reproduce (some of) their interesting properties.

HTML 4.01 - CSS 2 - Powered by Saverio Caminiti