On uniform randomness of the weight of the remaining edges of a graph after deleting some of them
-
05-11-2019 - |
题
Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring edges of $e$. An edge $e$ is locally subdominant if its weight is smaller than all of its neighbors. With this background Let we have the following algorithm,
for e in E
if w(e) is locally sub-dominant
delete e from the graph G
double weights of all e in N(e)
My question is after this loop ends what can we say about uniform randomness of the remaining edges. Are they still uniform random?
没有正确的解决方案
不隶属于 cs.stackexchange