Optimization Problems in Network Connectivity

Опубликовано 27 июля 2016, 23:51

Besides being one of the principal driving forces behind research in algorithmic theory for more than five decades, combinatorial optimization in graphs has assumed increased significance in recent times with the advent and large-scale use of a variety of real-life networks including communication networks connecting network elements, social and information networks connecting individuals and communities, and conceptual networks such as overlays. A fundamental objective in the study of such networks is to identify vulnerabilities in existing networks, and to design new networks that achieve desired robustness at minimum cost. This constitutes the area of graph connectivity algorithms. In this talk, I will give an overview of my contributions to this area of algorithmic research, focusing on the problems of graph sparsification (STOC '11), minimum cuts (SODA '09, SODA'08, STOC '07, SODA '07), and survivable network design (FOCS '11, SODA '11). The talk will be self-contained.