0 votes 0 votes Algorithms algorithms p-np-npc-nph + – Churchill Khangar asked Nov 22, 2018 • retagged Jun 11, 2022 by makhdoom ghaya Churchill Khangar 479 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Utkarsh Joshi commented Nov 22, 2018 reply Follow Share 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 votes 0 votes kumar.dilip commented Nov 22, 2018 reply Follow Share According to your explanation, It seems to be P. Why NP ?? 0 votes 0 votes Utkarsh Joshi commented Nov 22, 2018 reply Follow Share P is the subset of NP isn't it?kumar.dilip 0 votes 0 votes Please log in or register to add a comment.
