g show that the hamiltonian-path problem from exercise 34.2-6 can be solved in polynomial time on directed acyclic graphs. give
1 answer:
The efficient algorithm can be given in polynomial time.
For this particular problem ,we could find a polynomial time solution for it and then it is proven it could be solved in polynomial time.
1. You must have a source node with an in-degree of zero for a directed acyclic graph, so look for a path in the original graph G that has that value. Since each node must be visited, there is no solution if there are multiple nodes. However, the zero degree should be visited first, and if there are multiple points, there must be some nodes that cannot be visited initially.
2. Assuming that the left graph is G', remove the source node with in-degree zero and its surrounding edges to find the next node to start at.
3. As I mentioned in 1), there is no way to visit those nodes since their in-degree is zero and there should only be one to visit after its predecessor. If the left graph G' has more than two nodes or vertices with the in-degree of zero, then we could conclude that it is unsolvable.
4. Continue performing step 3 until we reach the endpoint, where there are no more nodes to visit. If there are some nodes that are not visited but we can't find an edge to get to them, then the problem cannot be solved; otherwise, we ought to have the answer.
We have discovered the answer to the Hamiltonian-path from the aforementioned steps.
its complexity is O(|E|+|V|) where E is number of edges and V is number of vertexes in directed acyclic graph because from to
, we must trace the vertices and their surrounding edges. It is completed in polynomial time, as we are aware.
To know more about Hamiltonian- path here:
#SPJ4
You might be interested in