China
Africa
Explore chapters and articles related to this topic
Simulated Annealing
Published in Nazmul Siddique, Hojjat Adeli, Nature-Inspired Computing, 2017
In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.
Modeling and Simulation Tools for Mobile Ad Hoc Networks
Published in Jonathan Loo, Jaime Lloret Mauri, Jesús Hamilton Ortiz, Mobile Ad Hoc Networks, 2016
Kayhan Erciyes, Orhan Dagdeviren, Deniz Cokuslu, Onur Yılmaz, Hasan Gumus
Another example would be the vertex cover problem in a graph. A vertex cover of a graph is the set of vertices S ϵ V such that any edge e is incident to at least one vertex in S. Finding a vertex cover of minimum size is NP-complete. For a distributed robot network such as a Special Weapons and Tactics (SWAT), finding a vertex cover is equivalent to placing robots at the corners of a maze such that every robot is in sight of at least another robot, which means all robots remain connected.
Network Flows and Applications
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
definition: Let G be a graph, and let C be a subset of the vertices of G. Then set C is a vertex cover of graph G if every edge of G is incident on at least one vertex in C.
On transitions in the behaviour of tabu search algorithm TabuCol for graph colouring
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2018
Regarding related NP-hard problems, an evolutionary algorithm for the set cover problem has been shown to provide a very good approximation of the optimum (Yu, Yao, & Zhou, 2012). For the vertex cover problem, iterated local search (Witt, 2012), hybrid algorithms (Friedrich, He, Hebbinghaus, Neumann, & Witt, 2009) and fixed-parameter evolutionary algorithms (Kratsch & Neumann, 2013) have been analysed. Analytical results have also been obtained for heuristics tackling the Euclidean travelling salesperson problem (Sutton & Neumann, 2012).
A primer on the application of neural networks to covering array generation
Published in Optimization Methods and Software, 2022
Ludwig Kampel, Michael Wagner, Ilias S. Kotsireas, Dimitris E. Simos
The work presented in [15] relies on a chain of mappings, reducing the set cover problem to a vertex cover problem on a graph, which again appears as the complement of an independent set problem on the same graph. The latter is finally solved using a Boltzmann neural network. For reasons of clarity, Figure 1 gives a high-level view of the procedure we are following to generate CAs using Boltzmann machines.