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

Main Article Content

Sankhadeep Chatterjee
Debarshi Banerjee

Abstract

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.

Downloads

Download data is not yet available.

Article Details

Section
Articles