On 29.05.2014 at 11:00 in S5, there is the following noon lecture:
Network Algorithms for Real-World Graphs
University of Waterloo
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010