On uniform randomness of the weight of the remaining edges of a graph after deleting some of them

cs.stackexchange https://cs.stackexchange.com/questions/98170

  •  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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top