Algorithms and Complexity Seminar
Thursday, May 18, 2006, 4-5:15pm in 32-G575.
Algorithmic Performance in Complex Networks
Milena Mihail (Georgia Tech.)
Complex networks, like the Internet, the WWW and peer-to-peer networks, are all-pervasive
and are growing at an unprecedented rate. It is therefore of
fundamental importance to study the scaling behavior of algorithms that run on
these networks, as well as develop
design principles that support efficient algorithms for these
networks. In this talk we
will study algorithmic issues such as routing on the Internet,
searching and crawling on the WWW, and the design of peer-to-peer
networks.
Unlike previous approaches to these issues which involved degree distributions, the small
world phenomenon etc., our
main technique relies on finding ways of determining and enforcing
coductance of the topologies underlying the graphs of these networks.
Host: Madhu Sudan