Abstract

to appear in Discrete Applied Mathematics.

The average expected value of a rooted graph, Monte Carlo calculation, and a power index for the voting game

by Masahiro Hachimori

Abstract

The expected value of a rooted graph is the expected value of the number of vertices reachable from the root when each edge is deleted independently with probability (1-p). The uniform expected value of a rooted graph is the average of the expected value assuming the probability p is taken uniformly at random from [0,1]. In this paper, after verifying that computing the uniform expected value of a rooted graph is #-P-hard, we propose a Monte Carlo method for computing the uniform expected value. We also discuss some applications of the proposed method for 0/1-valued monotone set functions.