Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

On the performance of edge coloring algorithms for cubic graphs

Berglin, Edvin LU (2014) EDA920 20132
Department 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:
author
Berglin, Edvin LU
supervisor
organization
course
EDA920 20132
year
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}},
}