Two algorithms for generating and ranking the family of solutions of a finite irreflexive relation |
| |
Authors: | Emmanuel Loukakis |
| |
Affiliation: | Department of Mechanical Engineering, School of Engineering, University of Thessalonkia, Thessalonika, Greece |
| |
Abstract: | The family of solutions, also known as 1-bases or kernels, of a finite irreflexive relation has a variety of many interesting applications. Furthermore, the decision as towhether the associated digraph posesses a solution belongs to the class of computationally intractable problems known as NP-complete. In this paper we present (a) a tree search algorithm to generate the family of solutions of a digraph and (b) a dynamic programming algorithm to generate the family of solutions ranked in increasing order of their cardinality. Extensive computational experience with the tree search algorithm on more than 1000 randomly generated digraphs ranging from 50 to 150 vertices and from 15% to 60% densities has shown that the proposed algorithm is effective. |
| |
Keywords: | Solutions 1-bases digraph finite irreflexive relation NP-complete tree search algorithm dynamic programming algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|