Algorithm

Engineering

Theoretical computer science

Vertex (graph theory)

Computer science

Mathematical optimization

Bounded function

Mechanical engineering

Graph

Mathematics

Vertex cover

Edge cover

Nash equilibrium

Mathematical analysis

Approximation algorithm

Cover (algebra)

The vertex cover of networks is a classical combinatorial optimization problem. In this paper, we investigate the vertex cover problem solved by the memory-based best response update rule, which can not converge to a strict Nash equilibrium (SNE) with memory length m =3D 1. To overcome this shortcoming, a bounded rational behavioral (BRB) update rule is newly proposed in this paper. We prove that the BRB with m =3D 1 can guarantee that the whole vertices' state converges to a SNE. The simulation is carried out to verify that the performance of the proposed BRB update rule on representative networks. Moreover, we also find that a better SNE will be achieved by increasing the selection intensity.

A Minimal Memory Game-Based Distributed Algorithm to Vertex Cover of Networks