SPECIAL-PURPOSE PROCESSOR FOR SEARCHING FOR HAMILTONIAN CYCLES IN GRAPHS

摘要

FIELD: information technology.;SUBSTANCE: special-purpose processor for searching for Hamiltonian cycles in graphs comprises N identical processor elements, each consisting of a register, 3 multiplexers, a down counter, 9 OR elements, 8 AND elements, 2 groups of AND elements, an RS flip-flop and a D flip-flop, 6 OR elements, 2 groups of OR elements, 5 AND elements, an RS flip-flop and 2 D flip-flops.;EFFECT: faster search for a Hamiltonian cycle in a graph owing to concurrent operation of processor elements and reducing the amount of memory used to a value required to store the vertex-adjacency matrix of the processed graph by querying the memory only for adjacency information of the processed pair of vertices of the graph.;5 dwg