Department of
Applied
Mathematics

Network Algorithms for Real-World Graphs

Andreas Feldmann

University of Waterloo

Abstract

In recent years, vast communication networks of interconnected processing units have emerged as a result of ever more affordable hardware. Two examples of this are the Internet and parallel computing architectures. Other kinds of networks playing a key role in our modern society are transportation networks, such as those arising from roads or railways. Some fundamental computational problems arising in such networks include finding bisections, balanced partitions, Steiner trees, and spanners. I will present algorithms to efficiently find solutions for these problems, that are tailored to graphs that model real-world settings. For some cases I will also show that the algorithms are best possible.