Campus Event Calendar

Event Entry

What and Who

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

Prachi Goyal
Indian Institute of Science, Bengaluru, India
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Thursday, 22 August 2013
30 Minutes
E1 4


We investigate the parameterized complexity of the following

edge coloring problem motivated by the problem of channel assignment
in wireless networks. For an integer q >= 2 and a graph G, the goal is to
find a coloring of the edges of G with the maximum number of colors
such that every vertex of the graph sees at most q colors. This problem
is NP-hard for q = 2, and has been well-studied from the point of view of
approximation. Our main focus is the case when q = 2, which is already
theoretically intricate and practically relevant. We show fixed-parameter
tractable algorithms for both the standard and the dual parameter, and
for the latter problem, the result is based on a linear vertex kernel.

Accepted at : MFCS 2013


Geevarghese Philip
--email hidden
passcode not visible
logged in users only

Geevarghese Philip, 08/19/2013 10:05
Geevarghese Philip, 08/19/2013 10:04 -- Created document.