The Algorithms Group has interests and expertise in most active areas of
current research within the design, analysis and applications of
Namely, its memebers conduct researches with particular emphasis on the
- 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
- 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