Clique-to-clique distance computation using a specific architecture

Abstract

In this paper, we present a new fast architecture to compute the distance between cliques in different graphs. The distance obtained is used as a support function for graph labelling using probabilistic relaxation techniques. The architecture presented consists on a pipe-lined structure which computes the distance between an input clique and k reference cliques. The number of processing elements needed is m2, and the number of cycles required to compute the distance is ni (being m the number of external nodes in the input clique, and ni the number of external nodes in the i-th reference clique). The processing elements are very simple basic cells and very simple communication between them is needed, which makes it suitable for VLSI implementation.