Campus Event Calendar
Event Entry
New for: D1
What and Who
Faster Exponential Time Algorithm for Edge Coloring Using 3 Colors
Lukasz Kowalik
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
-- Not specified --
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 16 June 2006
13:30
-- Not specified --
E1 4
rotunda 3rd floor
Saarbrücken
Abstract
We consider the edge-coloring problem, i.e. given a graph assign colors to edges so that incident edges get different colors (or, equivalently, partition graph into a number of matchings). Let Delta denote the largest vertex degree in the graph. Then trivially, Delta colors are needed. Surprisingly, Delta + 1 colors always suffice (Vizing's Theorem). However, distingushing between these two cases is NP-complete for Delta >= 3.
In the talk I will focus on the first NP-complete case: subcubic graphs (Delta=3). I will describe an O(1.344^n)-time algorithm which colors such graphs with 3 colors or reports that this is impossible. This improves over the previous O(1.415^n)-time algorithm by Beigel & Eppstein. I will try to present my algorithm as an illustration of some general currently used principles of designing and analyzing "fast" exponential-time algorithms.
Contact
Lukasz Kowalik
--email hidden
passcode not visible
logged in users only
Lukasz Kowalik, 06/16/2006 10:08
Lukasz Kowalik, 05/29/2006 12:07 -- Created document.
Lukasz Kowalik, 05/29/2006 12:07 -- Created document.