On the performance of edge coloring algorithms for cubic graphs
(2014) EDA920 20132Department of Computer Science
- Abstract (Swedish)
- This thesis visits the forefront of algorithmic research on edge coloring of cubic graphs. We select a set of algorithms that are among the asymptotically fastest known today. Each algorithm has exponential time complexity, owing to the NP-completeness of edge coloring, but their space complexities differ greatly. They are implemented in a popular high-level programming language to compare their performance on a set of real instances. We also explore ways to parallelize each of the algorithms and discuss what benefits and detriments those implementations hold.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/4359826
- author
- Berglin, Edvin LU
- supervisor
- organization
- course
- EDA920 20132
- year
- 2014
- type
- H2 - Master's Degree (Two Years)
- subject
- keywords
- edge coloring, graph algorithm, cubic graph, performance test, performance comparison
- language
- English
- id
- 4359826
- date added to LUP
- 2014-03-17 12:44:31
- date last changed
- 2014-09-04 08:29:47
@misc{4359826, abstract = {{This thesis visits the forefront of algorithmic research on edge coloring of cubic graphs. We select a set of algorithms that are among the asymptotically fastest known today. Each algorithm has exponential time complexity, owing to the NP-completeness of edge coloring, but their space complexities differ greatly. They are implemented in a popular high-level programming language to compare their performance on a set of real instances. We also explore ways to parallelize each of the algorithms and discuss what benefits and detriments those implementations hold.}}, author = {{Berglin, Edvin}}, language = {{eng}}, note = {{Student Paper}}, title = {{On the performance of edge coloring algorithms for cubic graphs}}, year = {{2014}}, }