Question

Discuss the Hamiltion circuit 1) sequential algorithm; 2) parallel algorithm; 3) discuss its time complexity.

Answer 1

Please Upvote, if you are impressed with the answer

If you have any doubt, you can comment. I will clarify

Answer:

Hamiltonian Circuit:

Hamiltonian circuit is also known as Hamiltonian cycle

A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. Being a circuit, it must start and end at the same vertex. A Hamiltonian path also visits every vertex once with no repeats, but does not have to start and end at the same vertex.

Unlike Euler paths and circuits, there is no simple necessary and sufficient criteria to determine if there are any Hamiltonian paths or circuits in a graph. But there are certain criteria which rule out the existence of a Hamiltonian circuit in a graph, such as- if there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit.

1.Sequential Algorithm:

A sequential algorithm or serial algorithm is an algorithm that is executed sequentially – once through, from start to finish, without other processing executing – as opposed to concurrently or in parallel.

2. Parallel Algorithm:

A parallel algorithm is an algorithm that can execute several instructions simultaneously on different processing devices and then combine all the individual outputs to produce the final result. The problem is divided into sub-problems and are executed in parallel to get individual outputs. Later on, these individual outputs are combined together to get the final desired output.

Time Complexity:

1.Hamiltonian circuit: Time complexity of this algorithm is O(2ⁿn²).

2. Sequential circuit: bestcase - O(1), worstcase - O(n)

3. Parallel Circuit: f(n) = O(g(n))