Theory Seminar: Edvin Berglin, Lund University - The performance of edge coloring algorithms for cubic graphs
Info about event
Time
Location
Nygaard 295
Organizer
Theory Seminar
On the performance of edge coloring algorithms for cubic graphs
Speaker: Edvin Berglin, Lund University
Time: Wednesday, February 19 at 14:15 to 15:00
Location: Nygaard-295
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.
Host: Gerth Stølting Brodal