Ximena Quintana

Advisor: Prof. Sergio Greco

Topic: Incremental algorithms for calculating the maximum flow

Abstract: Knowledge of calculating the maximum flow in graph theory is not new, but their importance is that there is currently a high demand for mathematical solutions to facilitate the planning, programming and control fields and projects in any field such as in traffic to avoid traffic congestion, collection and package delivery, supply network design, production planning, etc. which allows to develop decision making. In fact, these networks are by their very nature and large size is a serious limit on the applicability of computational techniques which operates exclusively in the main memory. In common operations such as inserts, deletes and updates you need to run from scratch each time there is a change, this strategy tends to be inadequate because it is unnecessary while the cost involved is high. Considering the above has come to the need to apply an algorithm to manage updates on a graph maximizing the incremental approach, and considering alternative ways before propagate changes to adjacent nodes. A subtopic is the study a maximum flow problem that can exploit the proposed incremental approach and apply the proposed approach to the development of algorithms working on graph database systems.

email: x.quintana@dimes.unical.it