A Novel Boolean Expression based Algorithm to find all possible Simple Paths between two nodes of a Graph
Sankhadeep Chatterjee, Debarshi Banerjee · International Journal of Advanced Research in Computer Science · 2014
A novel algorithm has been proposed to find all possible simple paths between any two given nodes of a graph which is a NP-hard problem. First a novel approach to represent a graph using Boolean operators has been structured. The unique Boolean expression is used to find all possible paths between any two nodes. The analysis of Boolean expression based representation of a graph reveals that the problem is in NP-hard. Further a necessary and sufficient condition is given to show that the problem is not NP-complete. A detail theoretical analysis and experimental results has been given in support of its ingenuity. Keywords: Boolean Transformation, Counting problems, Graph enumeration, NP-completeness, Satisfiability, Undecidability.