A REDUNDANCE AWARE ALGORITHM FOR THE RING PERCEPTION PROBLEM

Abstract

Following the guidelines proposed by R. Balducci and R. Pearlman [1] for an efficient exact solution of the Ring Perception Problem, a new approach based on 'prc-filtcring' technique is introduced to perceive rings in structures represented by 2-connected graphs. The resulting algorithm has proved to reduce both resources allocation and redundant information processing when dealing with chemical cases. Actual computing times have constantly shown a conspicuous reduction with respect to methods using hash-tables 12.3] to treat redundant information. Furthermore no user intervention to 'tune' effectiveness is required (e.g. hash-table dimensioning).