New answers tagged counting
1
Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?
The above answer considers the version of this problem where vertices cannot be visited multiple times. However it seems that the intention of the question is that vertices could be visited multiple times.
The number of such paths can be exponential in |V| and |E|, so they cannot be listed in polynomial time.
The problem of counting the number of such ...
3
Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?
This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero.
This problem is actually #P-hard wich is believed to be strictly harder than NP.
The version of the problem where you only look for the existence of such a path is called the longest path ...
Top 50 recent answers are included
