Distributed architecture for implementing fast parallel algorithms for two combinatorial optimization problems

Using the Parallel Substitution Algorithm, as a formal model of parallel computations, a distributed architecture is designed for implementation of the following two fast parallel algorithms: one for the maximal independent set problem and the other for the minimum weighted vertex cover problem. The former is a randomizing algorithm based on the Monte Carlo method, the latter is a deterministic approximation algorithm based on the primal-dual technique that consists of finding feasible solutions to the problem under consideration and its dual to be close to each other. The topology of the connections between the processors in the designed distributed architecture is similar to the topology of the graph in hand.