Department of Mathematics

Indian Institute Of Technology Madras , Chennai
  • Mathematics Department Shifted to NAC Office of the Department of Mathematics is moved from HSB to New Academic Complex (NAC) 5th and 6th Floor

Greedy Algorithm for Maximum Independent set and its generalization

Speaker : Dr. Sounaka Mishra (Department of Mathematics, IIT Madras)

22-03-2018

Abstract :

Tur\'{a}n's theorem says that sparse graphs have large independent sets. We discuss a proof of this theorem due to Erd\"{o}s. We make a similar statement for a generalization of maximum independent set problem. We will also mention other results about the algorithmic complexity of this generalization.

Key Speaker Dr. Sounaka Mishra (Department of Mathematics, IIT Madras)
Place NAC 522
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None