A Novel Boolean Expression based Algorithm to find all possible Simple Paths between two nodes of a Graph

Sankhadeep Chatterjee, Debarshi Banerjee


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.

Full Text:


DOI: https://doi.org/10.26483/ijarcs.v5i7.2277


  • There are currently no refbacks.

Copyright (c) 2016 International Journal of Advanced Research in Computer Science