Fast Sequential and Parallel Vertex Relabelings

作者：Kantabutra Sanpawat^*

来源：International Journal of Foundations of Computer Science, 2015, 26(1): 33-50.

DOI：10.1142/S0129054115500021

• Graph relabeling
• graph algorithms
• complexity

Given an undirected, connected, simple graph G = (V, E), two vertex labelings L-V and 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 theta(n(2)), where n is the number of vertices in G. In this article we study the VERTEX RELABELING PROBLEM on graphs K-m,K-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,K-m can be solved quickly in O(log m) time using or processors on an DREW PRAM. Additionally, we also show that the number of processors can be further reduced to m/log m 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 in while the processor complexities remain m and m/log m. We also show that when graphs are restricted to Km, 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 of 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.

• 出版日期2015-1