Department of Mathematics

Indian Institute Of Technology Madras , Chennai

The maximum weight independent set problem.

Speaker : Dr. T Karthick, ISI Chennai.

24-08-2016

Abstract :

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. In 1982, Alekseev showed that the M(W)IS problem remains NP-complete on H-free graphs, whenever H is connected, but neither a path nor a subdivision of the claw. In this talk, we will focus on H-free graphs, where H is a path nor a subdivision of the claw, and show that the MWIS problem can be solved in polynomial time in certain classes of these graphs.

Key Speaker Dr. T Karthick, ISI Chennai.
Place Madhava Hall
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None