The complexity of the evolution of GRAPH LABELINGS
We study the GRAPH RELABELING PROBLEM-given an undirected, connected, simple graph G = (V, E), two labelings l and l′ of G, and label mutation or flip functions determine the complexity of evolving the labeling l into l′. The transformation of l into l′ can be viewed as an evolutionary process gover...
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-57749188719&partnerID=40&md5=e4cbb7260ed054e71f2f969b4589347c http://cmuir.cmu.ac.th/handle/6653943832/5335 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chiang Mai University |
| Language: | English |
| Summary: | We study the GRAPH RELABELING PROBLEM-given an undirected, connected, simple graph G = (V, E), two labelings l and l′ of G, and label mutation or flip functions determine the complexity of evolving the labeling l into l′. The transformation of l into l′ can be viewed as an evolutionary process governed by the types of mutations or flips allowed. The number of applications of the function is the duration of the evolutionary period. The labels may reside on the vertices or the edges. We prove that vertex and edge relabeling have closely related computational complexities. Upper and lower bounds on the number of imitations required to evolve one labeling into another in a general graph are given. We also explore both vertex and edge relabeling with privileged labels, and resolve some open problems by providing precise characterizations of when these problems are solvable. Many of our results include algorithms for solving the problems, and in all cases the algorithms are polynomial-time. The problems studied have applications in areas such as bioinformatics, networks, and VLSI. © 2008 IEEE. |
|---|