Foreword 1
Foreword 2
Acknowledgments
Contents
1 Introduction
1.1 An Application: Biological Graph Analysis
1.2 Enumerating Stories
1.3 Enumerating Bubbles
1.4 Enumerating Cycles or Paths
1.5 Further Analysis: Enumerating Central and Peripheral Vertices
1.6 Basic Definitions and Notations
1.7 Structure of the Work
Part IEnumeration Algorithm Techniquesand Applications
2 Enumeration Algorithms
2.1 Introduction
2.2 Algorithmic Issues and Brute Force Approaches
2.3 Basic Algorithms
2.3.1 Backtracking
2.3.2 Binary Partition
2.3.3 Reverse Search
2.4 Amortized Analysis
2.4.1 Basic Amortization
2.4.2 Amortization by Children
2.4.3 Push Out Amortization
2.5 Data-Driven Speed up
3 An Application: Biological Graph Analysis
3.1 Introduction
3.2 Biological Networks
3.2.1 Protein-Protein Interaction Network
3.2.2 Metabolic Network
3.2.3 Gene Regulatory Network
3.2.4 De Bruijn Graph
3.3 Analysis and Enumeration of Biological Networks
Part IIThree Examples of EnumerationAlgorithms
4 Telling Stories: Enumerating Maximal Directed Acyclic Graphs with Constrained Set of Sources and Targets
4.1 Introduction
4.2 Preliminaries
4.3 Preprocessing the Graph
4.4 Finding Single Stories
4.5 Enumerating Stories
4.5.1 Enumerating Stories by Enumerating FASs
4.5.2 Enumerating Stories by Enumerating Permutations
4.6 Enumerating Stories: An Example
4.7 Alternative Definition of a Story
4.8 Conclusion and Open Problems
5 Enumerating Bubbles: Listing Pairs of Vertex Disjoint Paths
5.1 Introduction
5.2 Preliminaries
5.3 Turning Bubbles into Cycles
5.4 The Algorithm
5.5 Enumerating Bubbles: An Example
5.6 Proof of Correctness and Complexity Analysis
5.7 Avoiding Duplicate Bubbles
5.8 Conclusion and Open Problems
6 Enumerating Cycles and (s, t)-Paths in Undirected Graphs
6.1 Introduction
6.2 Preliminaries
6.3 Overview and Main Ideas
6.3.1 Reduction to Paths
6.3.2 Decomposition in Biconnected Components
6.3.3 Binary Partition Scheme
6.3.4 Introducing the Certificate
6.3.5 Recursion Tree and Cost Amortization
6.4 Amortization Strategy
6.5 Certificate Implementation and Maintenance
6.6 Enumerating Paths: An Example
6.7 Extended Analysis of Operations
6.7.1 Operation Right_Update(C, e)
6.7.2 Operation Left_Update(C,e)
6.8 Conclusion and Open Problems
Part IIIFurther Analysis
7 Enumerating Diametral and Radial Vertices and Computing Diameter and Radius of a Graph
7.1 Introduction
7.2 Overview on Centrality Analysis for Biological Networks
7.3 Computing the Diameter and Enumerating All the Diametral Vertices
7.3.1 Restricting to Undirected Graphs
7.3.2 Generalizing to Weighted Graphs
7.4 Computing the Radius and Enumerating All the Radial Vertices
7.5 Enumerating Diametral and Radial Vertices: An Example
7.6 Ad Hoc Bad Cases
7.7 Experiments
7.7.1 Directed Graphs
7.7.2 Undirected Graphs
7.7.3 Overall Results
7.8 Conclusion and Open Problems
8 Conclusions
References