The Exponential Time Complexity of Computing the Probability That a Graph Is Connected.
Thore HusfeldtNina TaslamanPublished in: IPEC (2010)
Keyphrases
- connected components
- graph representation
- computational complexity
- linear complexity
- worst case
- graph structure
- probability distribution
- homology generators
- neighborhood graph
- jump diffusion process
- computational cost
- exponential size
- graph theoretic
- graph theory
- average case complexity
- probability measure
- complexity analysis
- social networks
- bipartite graph
- graph matching
- structured data
- random walk
- special case
- search algorithm