# 对不确定图的可达性查询 -- algorithms 领域 和 graphs 领域 和 probability-theory 领域 和 union-find 领域 cs 相关 的问题

## Reachability queries on uncertain graphs

0

### 问题

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?

## 回答列表

5

[1]金，ruoming等。 "在不确定图中的距离约束可达性计算。" VLDB捐赠的程序 4.9（2011）：551-562。

I edited your question to make it self-contained.

The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community [1].

Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find whether two given vertices are reachable, therefore, lie in the same connected component or disjoint set. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem:

[1] Jin, Ruoming, et al. "Distance-constraint reachability computation in uncertain graphs." Proceedings of the VLDB Endowment 4.9 (2011): 551-562.

## 相关问题

3  为什么工会的时间复杂性 - 查找是$O（LGN）$只有“outge and等级”？  ( Why time complexity of union find is olgn with only union by rank )

1  关于Sedgewick and Wayne算法速金的复杂性分析  ( On the complexity analysis of quick union in algorithms by sedgewick and wayne )

0  DSU算法优化  ( Dsu algorithm optimization )

3  Union的有趣应用  ( Interesting applications of union find )

0  对不确定图的可达性查询  ( Reachability queries on uncertain graphs )

4  找到kruskal算法实现最坏情况运行时间的图表  ( Find a graph for which kruskals algorithm achieves worst case running time )

1  如何显示连接组件中的两个顶点处于同一组？ （BI条件）  ( How to show that two vertices in a connected component are in the same set bi )

0  给定N顶点和M边缘发现两个节点是否在同一连接的组件中？  ( Given n vertices and m edges find if two nodes are in the same connected compone )

6  拆分：维护动态图形连接信息，在边缘删除下  ( Split find maintaining dynamic graph connectivity information under edge delet )

3  如何了解kruskal的复杂性通过Quick-Union通过等级和路径压缩实现？  ( How to understand the complexity of kruskal implemented with quick union by rank )

1  为什么交换功能在Union找到算法中使用？排名或大小数组如何用于优化  ( Why swap function is use in union find algorithm how rank or size array is used )
void union_sets(int a, int b) { a = find_set(a); b = find_set(b); if (a != b) { if (size[a] < size[b]) swap(a, b); pa...

3  快速联合和启发式的大小  ( Quick union and heuristic by size )

0  在不相交的集合中测试成员资格的复杂性  ( Complexity of testing membership in a disjoint set )