Search results for "NP-complete"
showing 3 items of 3 documents
Solving NP-Complete Problems with Networks of Evolutionary Processors
2001
We propose a computational device based on evolutionary rules and communication within a network, similar to that introduced in [4], called network of evolutionary processors. An NP-complete problem is solved by networks of evolutionary processors of linear size in linear time. Some furher directions of research are finally discussed.
NP-completeness of the hamming salesman problem
1985
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
Whom to befriend to influence people
2020
Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person $v$ in the network has a certain threshold $t(v)$ for {\em activation}, i.e adoption of the product or idea. If $v$ has at least $t(v)$ activated neighbors, then $v$ will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This {\em Minimum Links} Problem has applications in viral marketing and the study of epidemics. Its solution can be…