Fast Sequential and Parallel Vertex Relabelings of K_m,m

Given an undirected, connected, simple graph G = (V,E), two vertex labelings L_V and L'_V of the vertices of G, and a label flip operation that interchanges a pair of labels on adjacent vertices, the Vertex Relabeling Problem is to transform G from L_V into L'_V using the flip operation. Agnarsson et al. showed solving the Vertex Relabeling Problem on arbitrary graphs can be done in θ(n²), where n is the number of vertices in G. In this article we study the Vertex Relabeling Problem on graphs K_m,m and introduce the concept of parity and precise labelings. We show that, when we consider the parity labeling, the problem on graphs K_m,m can be solved quickly in O(log m) time using m processors on an EREW PRAM. Additionally, we also show that the number of processors can be further reduced to in this case while the time complexity does not change. When the labeling is precise, the parallel time complexity increases by a factor of log m while the processor complexities remain m and . We also show that, when graphs are restricted to K_m,m, this problem can be solved optimally in O(m) time when the labeling is parity, and can be solved in O(m log m) time when the labeling is precise, thereby improving the result in Agnarsson et al. for this specific case. Moreover, we generalize the result in the case of precise labeling to the cases when L_V and L'_V can be any configuration. In the end we give a conclusion and a list of some interesting open problems.