Title   name
2018 Discrete Math 세미나
 
  Title
  Speaker   이의웅  
  Date 2018-11-13
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.
 
Abstract : In the k-cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. This problem has been studied various algorithmic perspectives including randomized algorithms, fixed-parameter tractable algorithms, and approximation algorithms. Their proofs of performance guarantees often reveal elegant structures for cuts in graphs.
It has still remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this talk, I will give an overview on recent progresses on both exact and approximation algorithms. Our algorithms are inspired by structural similarities between k-cut and the k-clique problem.