An Empirical Study on Networks Flows

• Grant number: 22/10215-3
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: October 01, 2022
• End date: September 30, 2024
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: Ricardo Araújo da Silva
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

Abstract

In the maximum flow problem, the goal is to determine how to send the largest possible amount of flow between two vertices of a network that have capacities in the arcs, so that no capacity is exceeded and no flow is lost. This problem is very relevant because it is useful in modeling a wide variety of other problems.This project has as objectives the study of algorithms for the maximum flow problem, as well as the implementation, testing and performance analysis of these algorithms, and the production of a technical report with the main results studied and obtained.In addition, we would like to present the empirical results obtained at some conference in the area, because, although the algorithms and their worst-case complexities are well known, their empirical performance on different types of instances is less addressed.Given the opportunity, we intend to extend the studies to other network flow problems or NP-hard problems.We emphasize that this scientific initiation also aims to introduce the candidate to the area of scientific research and complement his training in Computer Engineering, deepening his knowledge in the areas of combinatorial optimization and algorithm design and analysis.