Algorithm - 2023.2 English

Vitis Libraries

Release Date
2023.2 English

The implemented Maximal Independent Set (MIS) is based on a iterative method. The algorithm goes serveral rounds to traverse all vertexs for selecting vertexs into MIS set. For each round, label every available vertex with a random weights. Then, if the weights of current vertex is the smallest among its’ neighbours, this vertex is labeled into MIS set and unlabeled its’ neighbours at the same time. By running several times of the iteration, all vertexed would be traversed and labeled vertexs are grouped into MIS set. The output is the vertex list of MIS set.