skip to main content
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 · events · thesis defenses · 2010-2011 · 

Thesis Defense - Gallagher

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

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:40)