Laboratory for Networks and Applied Graph Theory

Welcome to the homepage of our laboratory. Here you will find out about research we are pursuing concerning the application of algorithms analysis and graph theoretic techniques to problems in the scientific study of computers and networks. We are particularly interested in applications of algorithms and graph theory to large-scale networks, Internet technologies,and network communication schemes. We are also interested in related computational problems such as graph drawing and modeling.

Demonstrations

• Models for Network Scalability - Geographic Models (Server Location - Interference/Threshold)
  
  • Distributed Models and Algorithms for Surviavbility in Network Routing -- abstract
  • Directional routing via generalized st-numberings -- abstract
• Peer-to-peer, Evolving Networks, and File Sharing Technology
  
  • Latency Effects on Reachability in Large-scale Peer-to-Peer Networks -- abstract -- full paper to appear in SPAA 2001.
  • Scalability Issues in Large Peer-to-Peer Networks - A Case Study of Gnutella-- abstract
  • Misha's Gnutella related research page
• Software Development
  • UC Toolbar - A Desktop Navigation tool for UC Electronic Resources - > Powerpoint
  • GUS (Graphs Underlying Systems) - under development
  • Misha's Java tools
  • UC-FISH -- Yanmu's File Sharing software homepage
• Network Encyclopedia - under development

Research Topics

• Peer-to-peer and Evolving networks research. Major issues arising in the development of large-scale peer-to-peer collaborative networking which are relevant to our research thrusts include, scalability and vulnerability, security and authentication, spontaneity and ease-of-use, synchronization among group activities, and responsiveness to granularity of the application.

• Distributed networks research is focused on issues of network management and design, in particular we study problems of network vulnerability , routing schemes, and congestion control. We are currently exploring new models for effective network routing, including dynamic routing, fault-tolerant routing, hybrid routing models, adversarial routing, and geographic/geometric models. 
• Scalable network algorithms research is focused on issues of designing and analyzing algorithms for effective information dissemination on the Internet and the national information infrastructure. These efforts are closely associated with our work on metacomputing and collective communication algorithms, which is aimed at providing system-level support for distributed and cluster-based computation models. We are exploring new algorithmic techniques for a variety of network communication primitives, such as broadcasting, multicasting, and gossiping schemes. 
• Intelligent Webcasting is an applied focus of our research. We are studying problems related to designing and building multicast networks, capable of delivering streaming media, using collections of geographically distributed servers. Please see our new project page for more information. 
• Development of graph theory tools and software for high-performance computing, including DAG level modeling of application software, Ad Hoc Network clustering using graph partitioning, and Graph theoretic based network design. 
• Graph drawing and graph modeling research is focused on issues of manipulating and displaying graphs using computers. The problems of graph drawing are related to embedding graphs, in 2- and 3-dimensional space, in a manner that can communicate structural information to the user. Our work in graph modeling makes use of LEDA, Stanford GraphBase, and other packages. 
• Dynamic graphs and hypergraphs research is focused on graph and hypergraph applications to logic programming and to stable and well-founded semantics. 
• Parallel algorithms and architectures research is focused on issues involving the application of parallel computation models. Parallel computers are recognized today as the unique architectural model for the design of the most powerful supercomputers. Our research efforts are focussed on designing and analyzing algorithms for these parallel computers, including a variety of grand challenge problems, problems in computational biology, and problems of parallel numeric algorithms. We also study the the design of interconnection networks and the logical mapping problems associated with parallel software solutions. 
• Applied mathematics research is focused on the foundations underlying the application areas discussed above. We are particularly interested in the mathematics associated with algebraic and potential theory convex embeddings and geometry, and graph connectivity and graph coloring.