eFficient Algorithms for NeTwork Analysis (FANTA)

Main goals, objectives and challenges

Many diverse natural or man-made systems are modeled as networks, capturing both the structure and the dynamics of the underlying system. Examples include but are not limited to the world-wide web, transportation, communication and social networks, databases, biological systems, circuits, and the control-flow of computer programs. The use of networks as a unified model for many diverse systems led to a surge of research interest in the analysis of graphs from many disparate areas of computer science and other disciplines. Despite the broad range of applications of network models, there are problems of fundamental importance that cut across different types of networks and different research areas. Underlying these practical problems, there are deep theoretical questions about network analysis and optimization problems such as connectivity, reachability, dominators, and cuts. Algorithms and data structures for such fundamental graph problems have been the subject of extensive research for decades. Nevertheless, the area of graph algorithms continues to attract a lot of attention and to produce many significant results related to the above problems. Furthermore, recent applications, as well as theoretical advances, motivate the study of novel variants of well-known problems. In this project, we will focus on the topics outlined above, from the perspective of both theory and practice. Our objective is to study novel problems and advance the state of the art in previously-studied problems along the following directions:

• Algorithms for connectivity and reachability problems on static and dynamic graphs.

• Network connectivity under failures.

• Survivable network design.

We aim to develop new algorithmic techniques, provide practical solutions for key problems in important application areas, and transfer advanced algorithmic technologies through experiments and algorithm engineering. In this framework, one big challenge is to design scalable algorithms (linear-time or close to linear-time), since algorithms with higher running times might be practically infeasible on today’s architectures for large-scale graphs.

Duration

December 2019 - June 2023 (36+6 months)