CS Events Monthly View

PhD Defense

On the Algorithmic Aspects of Tur√°n's Theorem

 

Download as iCal file

Thursday, June 08, 2017, 02:00pm

 

Tur√°n's Theorem gives an upper bound on the number of edges of n-node, K_r-free graphs, or equivalently it can be restated as that every n-node, m-edge graph has an independent set of size n^2/(n+2m). We illustrate how to apply Tur√°n's Theorem to algori

Speaker: Meng-Tsung Tsai

Bio

NULL

Location : CoRE A (301)

Committee

Prof. Martín Farach-Colton (Chair), Prof. Eric Allender, Prof. William Steiger, and Prof. Rezaul Chowdhury (Stony Brook U.)

Event Type: PhD Defense

Abstract: 

Organization

Dept. of Computer Science