Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D1
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Faster Exponential Time Algorithm for Edge Coloring Using 3 Colors
Speaker:Lukasz Kowalik
coming from:Max-Planck-Institut für Informatik - D 1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Language:-- Not specified --
Date, Time and Location
Date:Friday, 16 June 2006
Duration:-- Not specified --
Building:E1 4
Room:rotunda 3rd floor
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.

Name(s):Lukasz Kowalik
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Lukasz Kowalik, 06/16/2006 10:08 AM
  • Lukasz Kowalik, 05/29/2006 12:07 PM -- Created document.