Fast sequential and parallel vertex relabelings of K<inf>m,m</inf>

• Main Author: Kantabutra,S.
• Format: Article
• Published: World Scientific Publishing Co. Pte Ltd 2015
• Subjects: Computer Science (miscellaneous)
• Online Access: http://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=84928378705&origin=inward; http://cmuir.cmu.ac.th/handle/6653943832/39123
• Institution: Chiang Mai University

© 2015 World Scientific Publishing Company. Given an undirected, connected, simple graph G = (V,E), two vertex labelings L<inf>V</inf> and L'<inf>V</inf> 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<inf>V</inf> into L'<inf>V</inf> 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<inf>m,m</inf> and introduce the concept of parity and precise labelings. We show that, when we consider the parity labeling, the problem on graphs K<inf>m,m</inf> 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 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 m while the processor complexities remain m and m\log m. We also show that, when graphs are restricted to K<inf>m,m</inf> 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<inf>V</inf> and L'<inf>V</inf> can be any configuration. In the end we give a conclusion and a list of some interesting open problems.