engleski

A New Path Algebra for Finding Paths in Graphs

Path problems in graphs can generally be formulated and solved by using a suitable algebraic structure whose instances are called path algebras. Each type of path problem requires a different instance of the structure. In this paper we consider a new path algebra, which can be applied for finding one path between any pair of nodes in a graph. We prove that our proposed solution is correct and computationally efficient.

graph theory; directed graphs; path problems; path algebras; semirings; finding paths; computational complexity

nije evidentirano