Algorithms for Fundamental Problems in Computer Networks

Dr. Hsin-Hao Su


Data in networks are processed in different manners in different scenarios. In the traditional centralized setting, the whole network information is fed into a single device to compute the solution. In a large-scale network, the overhead of collecting all the information into a single machine is very expensive. In a distributed network such as the Internet, each node is an autonomous device which can communicate with its neighbors and perform local computation. In this case, the solution is computed through coordination among the nodes. On the other hand, in a network with mobile agents, they compute the solution by propagating and collecting necessary information. In this talk, I will review some recent progress on the fundamental problems such as matching and coloring under these settings. I will also talk about how agents estimate the density of their population in a network, where the motivation originated from ant colonies.