edited by
415 views
0 votes
0 votes
Q. consider the following problem:

a) Eulerian path

b) 2- SAT

c) Constraint reachibilty

d)graph coloring

number of problem which is polynomial solvable??

 i am get only b (2-SAT) somy answer is 1 but answer given 2 here also eulerian path  ?? how to appraoch these type of question Plz  explain??
edited by

1 Answer

1 votes
1 votes

we can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time

but if the question is asking to find the path itself, then its a NP complete

Related questions

1 votes
1 votes
2 answers
3
akankshadewangan24 asked Jun 20, 2017
2,001 views
P and NP concepts are there in gate syllabus?????????????????????????????????????????????
0 votes
0 votes
0 answers
4