#TITLE_ALTERNATIVE#
An f-coloring of a simple graph G = (V,E) is to color each edge in G so that, each color appears at each vertex v at most f(v) times where f : V → ℵ. Since f-coloring where f(v) = 1 for each vertex v ∈ V is NP-complete problem, then in general, f-coloring is NP-complete...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/8287 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| id |
id-itb.:8287 |
|---|---|
| spelling |
id-itb.:82872017-09-27T11:43:04Z#TITLE_ALTERNATIVE# HASBULLAH (NIM 10103010), ISMAIL Indonesia Final Project INSTITUT TEKNOLOGI BANDUNG https://digilib.itb.ac.id/gdl/view/8287 An f-coloring of a simple graph G = (V,E) is to color each edge in G so that, each color appears at each vertex v at most f(v) times where f : V → ℵ. Since f-coloring where f(v) = 1 for each vertex v ∈ V is NP-complete problem, then in general, f-coloring is NP-complete problem. Therefore, it is very unlikely that there exists an exact algorithm which solves the edge-coloring problem in polynomial time. This final project gives efficient algorithms to find edge-coloring and f-coloring for various classes of graphs such as wheel graphs, fan graphs and graphs with particular degeneracy, aboricity, and unicyclic index . Then, for other classes of graphs, we used heuristic algorithm. 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 |
An f-coloring of a simple graph G = (V,E) is to color each edge in G so that, each color appears at each vertex v at most f(v) times where f : V → ℵ. Since f-coloring where f(v) = 1 for each vertex v ∈ V is NP-complete problem, then in general, f-coloring is NP-complete problem. Therefore, it is very unlikely that there exists an exact algorithm which solves the edge-coloring problem in polynomial time. This final project gives efficient algorithms to find edge-coloring and f-coloring for various classes of graphs such as wheel graphs, fan graphs and graphs with particular degeneracy, aboricity, and unicyclic index . Then, for other classes of graphs, we used heuristic algorithm. |
| format |
Final Project |
| author |
HASBULLAH (NIM 10103010), ISMAIL |
| spellingShingle |
HASBULLAH (NIM 10103010), ISMAIL #TITLE_ALTERNATIVE# |
| author_facet |
HASBULLAH (NIM 10103010), ISMAIL |
| author_sort |
HASBULLAH (NIM 10103010), ISMAIL |
| title |
#TITLE_ALTERNATIVE# |
| title_short |
#TITLE_ALTERNATIVE# |
| title_full |
#TITLE_ALTERNATIVE# |
| title_fullStr |
#TITLE_ALTERNATIVE# |
| title_full_unstemmed |
#TITLE_ALTERNATIVE# |
| title_sort |
#title_alternative# |
| url |
https://digilib.itb.ac.id/gdl/view/8287 |
| _version_ |
1820664377137692672 |