Neighborhood principle driven ICF algorithm and graph distance calculations

Abstract. In the field of Boolean algebra there are many well known methods to optimize/analyze formulas of Boolean functions. This paper presents a non-conventional graph-based approach by describing the main idea of the Iterative Canonical Form (or ICF) [5,9] of a Boolean function, and introducing an algorithm that is capable of calculating the ICF. The algorithm is iteratively processing the neighboring nodes inside the \(n\)-cube. The iteration step count is a linear function of \(n\). Some novel efficient methods for computing distances by matching
non-complete bipartite graphs, derived from the ICF and named as ICF-graphs [4,9,10] are proposed. Different metrics between the ICF-graphs are introduced, such as weighted and normalized node count distances, and graph edit distance. Some recent results and application possibilities of the ICF-graph based distance calculations from the field of molecular systematics, ecology and medical diagnostics are discussed.