Approximation Algorithms for the Achromatic Number of Butterfly and Beneš Networks
Sharmila Mary Arul · Procedia Computer Science · 2020
Let G = (V,E) be a graph. Then the achromatic number for the graph is the largest integer m in such a way that there is a partition of V into disjoint independent sets (V 1 , V 2 ,…,V m ) satisfying the condition that for each pair of distinct sets V i , V j , V i ∪ V j is a dependent set in G . To determine the achromatic number for Butterfly and Beneš networks, in this paper we have presented the approximate algorithms.