Almost linear time algorithms for flows in graphs

• Grant number: 15/24747-3
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: February 01, 2016
• End date: December 31, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Marcel Kenji de Carli Silva
• Grantee: Victor Sanches Portella
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

This is the undergraduate research project of Victor Sanches Portella, under the supervision of Marcel Kenji de Carli Silva, at the Institute of Mathematics and Statistics of the University of São Paulo (USP), from 1/1/2016 to 31/12/2016 (12 months). The main goal of this project is the study of fast (almost linear-time) algorithms for flows in graphs based on sparsification, electrical networks, and other spectral methods. The project will involve very recent monographs and papers (from the last 5 years) and it will get the applicant acquainted with some modern, powerful techniques for algorithm design with broad application potential, approaching the state-of-the-art. One of the byproducts of this project will be a monograph about this subject. We believe that mastering these tools together with the experience of writing an academic text will be valuable to the applicant, who plans to join a graduate program upon graduating.