Please use this identifier to cite or link to this item:
Title: Graph relabeling with stacked labels
Authors: Pochara Patthamalai
Sanpawat Kantabutra
Authors: Pochara Patthamalai
Sanpawat Kantabutra
Keywords: Computer Science;Engineering
Issue Date: 30-Jul-2010
Abstract: This paper describes a new problem in graph theory called the GRAPH RELABELING WITH STACKED LABELS. Given a simple and connected graph G = (V, E), two labelings L and L' of G, the problem is to make a series of transformation from <G, L> to <G, L' >, where <G, L> is the graph G with labeling L. The transformation in consideration here is a flip operation. A flip operation allows a pair of stacked labels in two adjacent vertices to exchange places between vertices in a certain fashion. In this paper we show that this problem in general is insolvable. We precisely characterize the solvability for this problem when G is either a path graph or a tree and in the process we also have polynomial time algorithms to solve the problem in both cases. Additionally, we also show that our algorithm is exact and provably fastest in the case G is a path graph. Potential applications and open problems are also discussed.
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.

Items in CMUIR are protected by copyright, with all rights reserved, unless otherwise indicated.