Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Efficient Enumeration of all Connected Induced Subgraphs of a Large Undirected Graph

Maxwell, Sean T

Abstract Details

2014, Master of Sciences, Case Western Reserve University, Systems Biology and Bioinformatics.
In this work we investigate the problem of efficiently enumerating all connected induced subgraphs of an undirected graph. We show that the redundant computations in a depth first branch and bound search for subgraphs that satisfy a hereditary property can be reduced using an enumeration tree as a "memory" during the depth first search to avoid redundant rejections. This approach reduces the runtime of exhaustive search as well. Our method includes a proof of correctness and computational results on synthetic and real data sets demonstrating improved runtime over traditional depth first approaches.
Mark Chance, Phd (Committee Chair)
Mehmet Koyuturk, Phd (Advisor)
Harold Connamacher, Phd (Committee Member)
54 p.

Recommended Citations

Citations

  • Maxwell, S. T. (2014). Efficient Enumeration of all Connected Induced Subgraphs of a Large Undirected Graph [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1386363081

    APA Style (7th edition)

  • Maxwell, Sean. Efficient Enumeration of all Connected Induced Subgraphs of a Large Undirected Graph . 2014. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1386363081.

    MLA Style (8th edition)

  • Maxwell, Sean. "Efficient Enumeration of all Connected Induced Subgraphs of a Large Undirected Graph ." Master's thesis, Case Western Reserve University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=case1386363081

    Chicago Manual of Style (17th edition)