GAMA · Graph Algorithms and Massive Data Sets
FP6 — Marie Curie Actions (Human Resources and Mobility)
- Duration
- 2004-04-08 → 2006-04-07
- EU contribution
- €115,653
- Participants
- 1
- Scheme
- EIF
Lines connect the coordinator with its partners.
Results in brief
Final Activity Report Summary - GAMA (Graph algorithms and massive data sets)
A graph is a basic combinatorial structure consisting of a set of so-called vertices and a set of links between some pairs of the vertices. A typical example of graph is: each person in the world is a vertex, and each pair of persons is linked if they know each other (or if they are relatives or any other property one may choose). In particular, graphs are a generalisation of networks. The distance between two vertices of a graph is defined as the minimum number of links you have to follow to go from one vertex to the other one. A drawing (in the plane) of a graph is a representation where each vertex is assigned a point and each link is a path joining its vertices. Planar graphs, that is, graphs that can be drawn without two links crossing, are an important class of graphs that has been extensively studied before. They enjoy a rich amount of properties and structure, but, more importantly, they arise in many applications. An extension of planar graphs is graphs on surfaces, that is, graphs that can be drawn in a fixed surface without two links crossing each other. The objective of this project was to obtain new, efficient algorithms for solving problems whose input is a graph. Large part of the project has been devoted to algorithms for planar graphs and graphs on surfaces, and, more precisely, problems concerning distances. Several new results and techniques devoted to this area have been obtained. As a major achievement, we have shown how to improve the trade-off between the time needed to preprocess a planar graph and the time needed to report distances between its vertices.
Data: CORDIS, © European Union
Project objective
The design of graph algorithms plays a fundamental role to solve many of the computational problems that arise from several fields. The efficiency of an algorithm is a critical parameter that determinates its applicability, and it is becoming more and more critical nowadays when the amount of data and information is growing to sizes of terabytes (e.g. Internet search databases, geographical information systems, and bio informatics). For non-massive data sets, the efficiency directly depends on the number of elementary operations that the algorithm makes in main memory, but for massive data sets, the bottleneck of the computation is the number of times weave to probe (or access) the data through the memory hierarchy. In this work, the connection between information hidden in the data will be modelled in a graph-theoretical way giving us (massive) graphs that we want to deal with.Efficient, new graph algorithms will be developed that will take into account the trade-off between time and space in massive and non-massive data sets. According to the leading expertise of the host, emphasis will be put on techniques based on graph minors and topological methods. The researcher will receive advanced training in the methods and techniques commonly used in graph and external memory algorithms. Together with his previous work on computational geometry, the researcher will have acquired broad knowledge of a cross-section of discrete algorithms.
Original text from CORDIS.
Participants
- INSTITUT ZA MATEMATIKO, FIZIKO IN MEHANIKO · LJUBLJANACoordinatorSlovenia
Links
Data: CORDIS, © European Union