Department of Computer Science University of Colorado Boulder
 cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
 home | quick links | site map | who's where | cs a-z
home · events · thesis defenses · 2010-2011 ·

# Thesis Defense - Gallagher

9/2/2010
2:00pm-4:00pm
ECOT 831

Graph Connectivity: Approximation Algorithms and Applications to Protein-Protein Interaction Networks
Computer Science PhD Candidate

A graph is connected if there is a path between any two of its vertices and k-connected if there are at least k disjoint paths between any two vertices. A graph is k-edge-connected if none of the k paths share any edges and k-vertex-connected (or k-connected) if they do not share any intermediate vertices. We examine some problems related to k-connectivity and an application.

We have looked at the k-edge-connected spanning subgraph problem: given a k-edge-connected graph, find the smallest spanning subgraph that is still k-edge-connected. We improved two algorithms for approximating solutions to this problem. The first algorithm transforms the problem into an integer linear program, relaxes it into a real-valued linear program and solves it, then obtains an approximate solution to the original problem by rounding non-integer values. We have improved the approximation ratio by giving a better scheme for rounding the edges and bounding the number of fractional edges. The second algorithm finds a subgraph where every vertex has a minimum degree, then augments the subgraph by adding edges until it is k-edge-connected. We improve this algorithm by bounding the number of edges that could be added in the augmentation step.

We have also applied the idea of k-connectivity to protein-protein interaction (PPI) networks, biological graphs where vertices represent proteins and edges represent experimentally determined physical interactions. Because few PPI networks are even 1-connected, we developed algorithms to find the most highly connected subgraphs of a graph. We applied our algorithms to a large network of yeast protein interactions and found that the most highly connected subgraph was a 16-connected subgraph of membrane proteins that had never before been identified as a module and is of interest to biologists. We also looked at graphs of proteins known to be co-complexed and found that a significant number contained 3-connected subgraphs, one of the features that most differentiated complexes from random graphs.

 Committee: Debra Goldberg, Assistant Professor (Co-Chair) Harold (Hal) Gabow, Professor (Co-Chair) John Black, Associate Professor Andrzej Ehrenfeucht, Distinguished Professor Lawrence Hunter, University of Colorado School of Medicine San Skulrattanakulchai, Gustavus Adolphus College

 Department of Computer Science College of Engineering and Applied Science University of Colorado Boulder Boulder, CO 80309-0430 USA Questions/Comments? Send email to webmaster at cs.colorado.edu Engineering Center Office Tower ECOT 717 +1-303-492-7514 FAX +1-303-492-2844
 XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado Privacy · Legal · Trademarks May 5, 2012 (13:40)

.