吴文俊数学重点实验室组合与图论系列讲座之十七

报告题目：The alpha-Acyclic Hypergraph Decompositions of Complete Uniform Hypergraphs

报 告 人：张先得博士（新加坡南洋理工大学）

报告时间：12月13日（星期四） 下午4:30

报告地点：管理科研楼1316

摘要：Acyclic hypergraphs were introduced as a hypergraph analogue of trees in graphs. Besides being mathematically interesting, acyclic hypergraphs feature prominently in the study of problems in database theory and constraint satisfaction. There is a natural bijection between database schemas and hypergraphs, where each attribute of a database schema corresponds to a vertex in a hypergraph and each relation of attributes corresponds to an edge. One of the primary reasons for the desirability of α-acyclicity in database schemas is that there are important problems that are NP-hard on general database schemas but which becomes polynomial-time solvable when restricted to α-acyclic instances. When faced with such computationally intractable problems on a general database schema, it is natural to decompose it into α-acyclic instances on which efficient algorithms can be applied. This talk will give several methods of decomposing a complete uniform hypergraph into acyclic sub-hypergraphs by using tools in combinatorial design theory.

张先得博士简介：2004年获河南大学学士学位；2009年获浙江大学博士学位。2009.8－2011.7在新加坡南洋理工大学（Nanyang Technological University）做博士后；2011.8－2012.7 在澳大利亚莫纳什大学（Monash University）做博士后；2012.8－至今回新加坡南洋理工大学做博士后。主要研究兴趣为：组合设计及其在编码、密码、计算机、生物信息与统计等领域的应用，在国际专业顶尖杂志发表学术论文15篇。

主办单位：0029cc金沙贵宾会 
         中科院吴文俊数学重点实验室 

欢迎感兴趣的师生参加!