The Markov Blanket of a random variable is the minimum conditioning set of variables that makes the variable independent of all other variables. A core step to estimate the Markov Blanket is the identification of the Parents and Children (PC) variable set. This paper propose a novel Parents and Children discovery algorithm, called Max-Min Random Walk Parents and Children (MMRWPC), which improves the computational burden of the classical Max-Min Parents and Children method (MMPC). The improvement was achieved with a series of modifications, including the introduction of a random walk process to better identifying conditioning sets in the conditional independence (CI) tests, implying in a significantly reduction of expensive high-order CI tests. In a series of experiments with data sampled from benchmark Bayesian networks we show the suitability of the proposed method.