Thursday, May 13

Massive Graphs: Algorithms, Applications, and Open Problems

9:15 AM-10:00 AM
Room: Capitol Center/South
Chair: Randall Bramley, Indiana University, Bloomington

In a traditional telephone network, operations data are represented by a weighted, directed multigraph. Each node is a telephone number, and each arc from node A to node B is a call made by A to B. The arcs are weighted to reflect the fact that some calls are longer than others, and the structure is a multigraph because there can be more than one arc from A to B. Technical tools to maintain and analyze massive call graphs can be a significant competitive advantage to a company.

Massive graphs now pose formidable technical challenges. Increased calling volume creates one class of problems: The call graphs of today and tomorrow are sufficiently huge in comparison to those of yesterday that standard graph problems cannot be solved by tweaking yesterday's solutions or by running them on modern equipment. Fundamentally new solutions and perhaps new problem formulations are needed. More open-ended challenges are posed by the ascendance of Internet-generated data. Despite their increasing importance, the multigraphs for Internet traffic are not nearly as well understood as those for telephone traffic; indeed, it is not even clear that a weighted, directed multigraph is the right abstraction of Internet data. The speaker will present recent progress and open problems in both of these areas.

Joan Feigenbaum
AT&T Laboratories, Research

AN99 Home


Program Updates

Speaker Index




MMD, 1/26/99