Algorithm for Determining Locating-chromatic Number of Trees
The concept of the locating-chromatic number for graphs was introduced by Chartrand et al (2002). Determination of the locating-chromatic number of an arbitrary graph is an NP-complete Problem. This means that there is no efficient algorithm to determine the locating-chromatic number of any given...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/38771 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| id |
id-itb.:38771 |
|---|---|
| spelling |
id-itb.:387712019-06-17T13:50:05ZAlgorithm for Determining Locating-chromatic Number of Trees Imulia Dian Primaskun, Devi Indonesia Theses Locating-chromatic number, trees, local-end branch, end-path. iii INSTITUT TEKNOLOGI BANDUNG https://digilib.itb.ac.id/gdl/view/38771 The concept of the locating-chromatic number for graphs was introduced by Chartrand et al (2002). Determination of the locating-chromatic number of an arbitrary graph is an NP-complete Problem. This means that there is no efficient algorithm to determine the locating-chromatic number of any given graph. However, we can arrange a special algorithm to determine the locating-chromatic number of a certain class of graphs. In this paper, we focus on an algorithm to determine the upper bound of the locating-chromatic number of any tree. This algorithm works better than the one given by Furuya and Matsumoto (2019). Let T be a tree. A vertex u of T with degree at least 3 is a local-end branch if there are at least two end-path from u. Palm of T is local-end branch with its end-path. This algorithm is based on considering palms on a tree. text |
| institution |
Institut Teknologi Bandung |
| building |
Institut Teknologi Bandung Library |
| continent |
Asia |
| country |
Indonesia Indonesia |
| content_provider |
Institut Teknologi Bandung |
| collection |
Digital ITB |
| language |
Indonesia |
| description |
The concept of the locating-chromatic number for graphs was introduced by
Chartrand et al (2002). Determination of the locating-chromatic number of
an arbitrary graph is an NP-complete Problem. This means that there is no
efficient algorithm to determine the locating-chromatic number of any given graph.
However, we can arrange a special algorithm to determine the locating-chromatic
number of a certain class of graphs.
In this paper, we focus on an algorithm to determine the upper bound of the
locating-chromatic number of any tree. This algorithm works better than the one
given by Furuya and Matsumoto (2019). Let T be a tree. A vertex u of T with
degree at least 3 is a local-end branch if there are at least two end-path from u. Palm
of T is local-end branch with its end-path. This algorithm is based on considering
palms on a tree. |
| format |
Theses |
| author |
Imulia Dian Primaskun, Devi |
| spellingShingle |
Imulia Dian Primaskun, Devi Algorithm for Determining Locating-chromatic Number of Trees |
| author_facet |
Imulia Dian Primaskun, Devi |
| author_sort |
Imulia Dian Primaskun, Devi |
| title |
Algorithm for Determining Locating-chromatic Number of Trees |
| title_short |
Algorithm for Determining Locating-chromatic Number of Trees |
| title_full |
Algorithm for Determining Locating-chromatic Number of Trees |
| title_fullStr |
Algorithm for Determining Locating-chromatic Number of Trees |
| title_full_unstemmed |
Algorithm for Determining Locating-chromatic Number of Trees |
| title_sort |
algorithm for determining locating-chromatic number of trees |
| url |
https://digilib.itb.ac.id/gdl/view/38771 |
| _version_ |
1822925108809826304 |