MODELAGEM E OTIMIZAÇÃO DE FLUXO EM UMA REDE REAL CONECTADA

Abstract

In this work, we approached the maximum flow problem from the graph theory perspective with the goal of providing a software implementation of an algorithmic solution to the problem for later use in optimization of network design and IP routing. Initially,we bring context and definition to the problem. Next, we present the studied algorithms, the methodology and the executed experiments. We coded two solutions to this problem from the literature: The Ford-Fulkerson algorithm and the Edmonds-Karp algorithm.A system in the form of a fiber optic network was modeled as a graph and the algorithms were applied to the model as proof of concept.Additionally, to empirically evaluate the algorithms’ correctness and performance, we made a random graph base with varying sizes and edge densities and ran the algorithms on those. The comparison of the results show that the Edmonds-Karp algorithm has greater performance.

Keywords

• Maximum flow
• Optimization of systems
• Graph theory