网站旧版 | English


当前位置: ag视讯 > 学术报告 > 正文


ag视讯:2015-04-29 编辑: 来源:


Graph Modification Problems and Their Parameterized Complexity

报告人: Dr. Yinxin Cao(操宜新)  Research Assistant Professor Department of ComputingHong Kong Polytechnic University

时间: 429日上午10:00——12:00

地点: App园校区新教师办公楼(医务室旁边)二楼会议室

主持人:朱大铭 教授

Abstract:  We are given as input a graph G, and the goal is to apply certain operations on G (such as vertex deletions, edge deletions, and/or additions) in order to obtain a graph G' with some particular property. Graphs play an important role in data modeling. They often have some specific properties, which, however, don't exhibit because of the existence of errors. Here modifications are used to detect the errors, and most graph modification problems have been formulated in this way.  Since many hard problems, including clique and coloring, become tractable on some special graphs, graph modification problems to these special graphs can be used as subroutines to solve these problems. Moreover, graph modification problems have also been associated with sparse matrix computation, and are known to be equivalent to various classic computational problems. We focus on their parameterized computation. This talk will review recent exciting progress in this direction.


Bio: Dr. Yixin Cao is a Research Assistant Professor at Department of Computing, Hong Kong Polytechnic University. Before taking the current position, he was a research fellow at Institute for Computer Science and Control, Hungarian Academy of Sciences. He has been visiting scholar in Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University. His general research interests are in graph algorithms, combinatorial optimization, and their usages in social networks.


Dr. Cao received the B.E. degree in automation from Harbin Engineering University, China in 2000, the M.Sc. degree in computer science from Beihang University, China in 2003, and Ph.D. degree in computer science from Texas A&M University, USA in 2012.


  • ag视讯官网
  • 青岛校区
  • 本科生院
  • 研究生院
  • 党委研究生工作部
  • 党委学生工作部、武装部


地址: 山东省青岛市即墨区滨海公路72号







XML 地图 | Sitemap 地图