Speaker : Prof. Sounaka Mishra(IIT Madras)
Title: Approximation algorithm for node deletion problems on bipartite graphs
Abstract: Here we consider node deletion problems associated with non-trivial hereditary graph properties $\pi$ having finite forbidden graph characterizations. These kinds of minimization problems are approximable with a constant factor and are APX-complete. If the input graphs are restricted to bipartite graphs then algorithms with better approximation factors can be designed. We will discuss these algorithms along with some other associated problems.
Venue: MZ 195 (Committee Room), Department of Mathematics
Speaker: Prof Sounaka Mishra.
https://math.iitm.ac.in/sounak.
Date and Time: September 16(Friday), at 15:30 hrs