PARALLEL INDEPENDENT SETS
“High Performance Computing
Acknowledgment: -
I study computer science and engineering at Bennett University. In order to write a paper for my High-Performance Computing course, I conducted this experiment.
Introduction: -
Let me first define an independent set before moving on. independent set graph, or G S is any vertices’ subset. S V that doesn’t have any nearby vertices (V, E).
Real-World Examples: -
In many different technological fields, including engineering and computer science, parallel independent is used to resolve complex problems. In biotech engineering, genetic analysis is a real-world example of a parallel independent set.
Algorithm: -
Now let’s start the heuristic part of the procedure.
A Parallel independent set can be computed using a randomized method. Following are the steps:
(1) Toss one cent for each active node. A node will receive a head if its chance is 0.5; otherwise, it will receive a tail. The independent set is expanded if the penny lands on the head. It will be eliminated from the group if it has a tail.
(2) The tail would separate each head from each other in accordance with the norm. The provided node and its neighbor must be changed to tail if they are both heads.
Work and Span: -
Ok let’s examine the work and duration for this algorithm:
The Project entails:
W(n): -> n
D(n): -> 1 or log n
That would be the work and span foe the algorithm.
Pseudo — Code: -
The Parallel Independent sets’ pseudo-Code seems to be as pursues:
A much more extensive pseudo-Code for the Parallel Independent sets is provided below:
Example: -
Get Solankiaryan’s stories in your inbox
Join Medium for free to get updates from this writer.
Now let’s get to the illustration for the Parallel Independent set.
There are no two neighboring vertices since, as seen in this example, the adjacent vertex of 4 is 2 and 2 is not a member of set I. The following number is 7, and 1 is also not in set I. It is, however, near to 7 and hence forms a vertex. The same is true for vertex 3 and vertex 6, whose neighbors are vertices 5 and 8, which are not present in I.
So, here’s another example to help you understand our algorithm: -
Set I in this figure has the number 3, which is an appropriate response, because adjacent vertices 1 and 5 are not present. The following acceptable response for its neighboring vertex 2, which is likewise missing from set I, is 4, which is also close by. Although 6 is the right response, it is erroneous because set I also contains 8’s neighboring vertex. Only one of the two should be added to my collection (6 or 8). After that, only set I will be referred to as a parallel independent set.
Interesting Fact: -
Do anyone of you know how many vertices typically make up the independent set?
It would be 1/4 n as the response.
Conclusion: -
For this essay, I looked at both parallel and serial independent sets. Parallel independent sets, a practical example, parallel pseudocodes, how to apply an algorithm to answer a query about a parallel independent set, work and span for the approach, and a fascinating fact have all been covered in addition to being defined.”
REFERENCES: -
1- Independent Set — from Wolfram MathWorld
2- Parallel Structure Examples | YourDictionary
3- http://202.240.109.17/publications/pdf/independentset.pdf
4- https://epubs.siam.org/doi/abs/10.1137/0218029
5- Maximal Independent Vertex Set — from Wolfram MathWorld
6- Maximal Independent Set — from Wolfram MathWorld
7- https://algo2.iti.kit.edu/lamm/theses/tom_george.pdf
8- https://dl.acm.org/doi/abs/10.1145/22145.22146
9- https://www.sciencedirect.com/science/article/pii/0196677486900192
