A connectionist solution for vertex cover problems

Summary form only given, as follows. A connectionist model is described for solving computationally difficult minimum vertex cover problems (VCPs). In this model, nodes of the network represent vertices and links represent edges of a given graph. A competitive activation mechanism is used to carry out the computation where vertices are competing not by explicit inhibitory links, but through common resources (edges). Instead of capturing the optimality through a global energy function, the global constraints of a solution were broken down to local constraints which in turn lead to a heuristic activation function governing the node behavior. Simulation results showed that this model yielded very high accuracy and significantly outperformed some sequential approximation algorithm.<>