The graph relabeling problem and its variants
Graph labeling is a classic problem in mathematics and computing. In this paper we study an interesting set of graph labeling problems which were first introduced by Kantabutra [12]. The general problem, here called the GRAPH RELABELING PROBLEM, is to take an undirected graph G = (V, E), two labelin...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
2014
|
| Online Access: | http://www.scopus.com/inward/record.url?eid=2-s2.0-52949107176&partnerID=40&md5=6eb3285463f32b7f8578ac4937b8b2f9 http://cmuir.cmu.ac.th/handle/6653943832/5468 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Language: | English |
| id |
th-cmuir.6653943832-5468 |
|---|---|
| record_format |
dspace |
| spelling |
th-cmuir.6653943832-54682014-08-30T02:56:34Z The graph relabeling problem and its variants Agnarsson G. Greenlaw R. Kantabutra S. Graph labeling is a classic problem in mathematics and computing. In this paper we study an interesting set of graph labeling problems which were first introduced by Kantabutra [12]. The general problem, here called the GRAPH RELABELING PROBLEM, is to take an undirected graph G = (V, E), two labelings l1 and l2 of G, and a label switching function f and then to determine the complexity of transforming the labeling l1 into l2 using f. We define several variants of the problem and discuss their complexity. We give tight bounds for one version of the problem on chains, and show another version is NP-complete. These problems have applications in areas such as bioinformatics, networks, and VLSI. ©2008 IEEE. 2014-08-30T02:56:34Z 2014-08-30T02:56:34Z 2008 Conference Paper 1424421012; 9781424421015 10.1109/ECTICON.2008.4600370 73753 http://www.scopus.com/inward/record.url?eid=2-s2.0-52949107176&partnerID=40&md5=6eb3285463f32b7f8578ac4937b8b2f9 http://cmuir.cmu.ac.th/handle/6653943832/5468 English |
| institution |
Chiang Mai University |
| building |
Chiang Mai University Library |
| country |
Thailand |
| collection |
CMU Intellectual Repository |
| language |
English |
| description |
Graph labeling is a classic problem in mathematics and computing. In this paper we study an interesting set of graph labeling problems which were first introduced by Kantabutra [12]. The general problem, here called the GRAPH RELABELING PROBLEM, is to take an undirected graph G = (V, E), two labelings l1 and l2 of G, and a label switching function f and then to determine the complexity of transforming the labeling l1 into l2 using f. We define several variants of the problem and discuss their complexity. We give tight bounds for one version of the problem on chains, and show another version is NP-complete. These problems have applications in areas such as bioinformatics, networks, and VLSI. ©2008 IEEE. |
| format |
Conference or Workshop Item |
| author |
Agnarsson G. Greenlaw R. Kantabutra S. |
| spellingShingle |
Agnarsson G. Greenlaw R. Kantabutra S. The graph relabeling problem and its variants |
| author_facet |
Agnarsson G. Greenlaw R. Kantabutra S. |
| author_sort |
Agnarsson G. |
| title |
The graph relabeling problem and its variants |
| title_short |
The graph relabeling problem and its variants |
| title_full |
The graph relabeling problem and its variants |
| title_fullStr |
The graph relabeling problem and its variants |
| title_full_unstemmed |
The graph relabeling problem and its variants |
| title_sort |
graph relabeling problem and its variants |
| publishDate |
2014 |
| url |
http://www.scopus.com/inward/record.url?eid=2-s2.0-52949107176&partnerID=40&md5=6eb3285463f32b7f8578ac4937b8b2f9 http://cmuir.cmu.ac.th/handle/6653943832/5468 |
| _version_ |
1681420431429468160 |