Network Algorithms and Complexity

Code 446
Semester Spring
Class Hours - Lab Hours 3 - 0
Lecturers Dimitris Fotakis, Aris Pagourtzis
Links Course's Website


Theoretical foundations of network problems. Computational complexity and approximability of relevant graph-theoretic problems: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling. Distributed networks: leader election, broadcast, secret sharing, Byzantine agreement. Communication protocols for wireless ad hoc networks. Optical networks: routing and wavelength assignment, multi-fiber networks. Routing protocols. Selfish routing, "price of anarchy", Nash equilibria, auctions. Autonomous agents: rendezvous, coordination, explorations, fault discovery, navigation.