東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Graph connectivity: Approximation al...

Gallagher, Suzanne Renick.

Linked to FindBook

Google Book

Amazon

博客來

Graph connectivity: Approximation algorithms and applications to protein-protein interaction networks.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Graph connectivity: Approximation algorithms and applications to protein-protein interaction networks./
Author:	Gallagher, Suzanne Renick.
Description:	276 p.
Notes:	Source: Dissertation Abstracts International, Volume: 72-02, Section: B, page: 0973.
Contained By:	Dissertation Abstracts International72-02B.
Subject:	Biology, Bioinformatics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3433292
ISBN:	9781124386799

Graph connectivity: Approximation algorithms and applications to protein-protein interaction networks.
Gallagher, Suzanne Renick.

Graph connectivity: Approximation algorithms and applications to protein-protein interaction networks. - 276 p.

Source: Dissertation Abstracts International, Volume: 72-02, Section: B, page: 0973.

Thesis (Ph.D.)--University of Colorado at Boulder, 2010.

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.

ISBN: 9781124386799Subjects--Topical Terms:

1018415
Biology, Bioinformatics.

Graph connectivity: Approximation algorithms and applications to protein-protein interaction networks.
LDR:03352nam 2200361 4500 001 1401123
005 20111013150258.5
008 130515s2010 ||||||||||||||||| ||eng d
020 $a 9781124386799
035 $a (UMI)AAI3433292
035 $a AAI3433292
040 $a UMI $c UMI
100 1 $a Gallagher, Suzanne Renick. $3 1680236
245 1 0 $a Graph connectivity: Approximation algorithms and applications to protein-protein interaction networks.
300 $a 276 p.
500 $a Source: Dissertation Abstracts International, Volume: 72-02, Section: B, page: 0973.
500 $a Advisers: Harold Gabow; Debra S. Goldberg.
502 $a Thesis (Ph.D.)--University of Colorado at Boulder, 2010.
520 $a 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.
520 $a We have looked at the k-edge-connected spanning subgraph problem: given a k-edge-connected graph, find the smallest subgraph that includes all vertices and 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.
520 $a 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 have looked for highly connected subgraphs of these graphs. 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.
590 $a School code: 0051.
650 4 $a Biology, Bioinformatics. $3 1018415
650 4 $a Computer Science. $3 626642
690 $a 0715
690 $a 0984
710 2 $a University of Colorado at Boulder. $b Computer Science. $3 1018560
773 0 $t Dissertation Abstracts International $g 72-02B.
790 1 0 $a Gabow, Harold, $e advisor
790 1 0 $a Goldberg, Debra S., $e advisor
790 1 0 $a Black, John R. $e committee member
790 1 0 $a Ehrenfeucht, Andrzej $e committee member
790 1 0 $a Hunter, Lawrence $e committee member
790 1 0 $a Skulrattanakulchai, San $e committee member
790 $a 0051
791 $a Ph.D.
792 $a 2010
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3433292