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...
Saved in:
Main Authors: | , |
---|---|
Format: | Conference Proceeding |
Published: |
2018
|
Subjects: | |
Online Access: | https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77954891969&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/50720 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Chiang Mai University |
id |
th-cmuir.6653943832-50720 |
---|---|
record_format |
dspace |
spelling |
th-cmuir.6653943832-507202018-09-04T04:45:55Z Graph relabeling with stacked labels Pochara Patthamalai Sanpawat Kantabutra Computer Science Engineering 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. 2018-09-04T04:44:41Z 2018-09-04T04:44:41Z 2010-07-30 Conference Proceeding 2-s2.0-77954891969 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77954891969&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/50720 |
institution |
Chiang Mai University |
building |
Chiang Mai University Library |
country |
Thailand |
collection |
CMU Intellectual Repository |
topic |
Computer Science Engineering |
spellingShingle |
Computer Science Engineering Pochara Patthamalai Sanpawat Kantabutra Graph relabeling with stacked labels |
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 Proceeding |
author |
Pochara Patthamalai Sanpawat Kantabutra |
author_facet |
Pochara Patthamalai Sanpawat Kantabutra |
author_sort |
Pochara Patthamalai |
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 |
2018 |
url |
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77954891969&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/50720 |
_version_ |
1681423640726339584 |