0 0 votes Algorithms algorithms p-np-npc-nph + – Churchill Khangar 804 views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Utkarsh Joshi commented Nov 22, 2018 reply Follow flag Assuming that the adjacency matrix representation of the graph is given, For the given problem, we have to find, A1 A2, A3, A4........Ak. This can take k* n3 time. And after each step, we just have to check whether there is '1' present in any of these A1, A2, A3,.....Ak matrices for all pair of vertices. We can do this everything in theta(2*k*n3) time. Hence this will come under P and NP. 0 0 replyShare kumar.dilip commented Nov 22, 2018 reply Follow flag According to your explanation, It seems to be P. Why NP ?? 0 0 replyShare Utkarsh Joshi commented Nov 22, 2018 reply Follow flag P is the subset of NP isn't it?kumar.dilip 0 0 replyShare Please log in or register to add a comment.
