Graph relabeling with stacked labels

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 g...

Full description

Saved in:
Bibliographic Details
Main Authors: Patthamalai P., Kantabutra S.
Format: Conference or Workshop Item
Language:English
Published: 2014
Online Access:http://www.scopus.com/inward/record.url?eid=2-s2.0-77954891969&partnerID=40&md5=a5368c8ef2d4ac7922dc6fafe1a6a5d0
http://cmuir.cmu.ac.th/handle/6653943832/6232
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
Language: English
id th-cmuir.6653943832-6232
record_format dspace
spelling th-cmuir.6653943832-62322014-08-30T03:23:59Z Graph relabeling with stacked labels Patthamalai P. Kantabutra S. 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. 2014-08-30T03:23:59Z 2014-08-30T03:23:59Z 2010 Conference Paper 9.78975E+12 81197 http://www.scopus.com/inward/record.url?eid=2-s2.0-77954891969&partnerID=40&md5=a5368c8ef2d4ac7922dc6fafe1a6a5d0 http://cmuir.cmu.ac.th/handle/6653943832/6232 English
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
language English
description 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.
format Conference or Workshop Item
author Patthamalai P.
Kantabutra S.
spellingShingle Patthamalai P.
Kantabutra S.
Graph relabeling with stacked labels
author_facet Patthamalai P.
Kantabutra S.
author_sort Patthamalai P.
title Graph relabeling with stacked labels
title_short Graph relabeling with stacked labels
title_full Graph relabeling with stacked labels
title_fullStr Graph relabeling with stacked labels
title_full_unstemmed Graph relabeling with stacked labels
title_sort graph relabeling with stacked labels
publishDate 2014
url http://www.scopus.com/inward/record.url?eid=2-s2.0-77954891969&partnerID=40&md5=a5368c8ef2d4ac7922dc6fafe1a6a5d0
http://cmuir.cmu.ac.th/handle/6653943832/6232
_version_ 1681420575115837440