讲座主题：The complexity of total edge domination and some related results on trees
主讲人：徐守军
工作单位：兰州大学
讲座时间：2019年5月31日8:30
讲座地点：数学院大会议室
主办单位：99精品视频在线观看数学与信息科学学院
内容摘要：
In this talk, we prove that the total edge dominating problem is NP-complete for bipartite graph with maximum degree 3, and design a linear-time algorithm for solving this problem in a tree. We also present sharp upper and lower bounds on the total edge domination number in trees in terms of edge domination number and then characterize the extremal trees.
主讲人介绍：
徐守军，兰州大学数学与统计学院教授、副院长、博士生导师，中国运筹学会图论组合分会青年理事。主要研究方向：图论及其应用、离散算法、组合算法和优化、复杂网络。在SIAM J Discrete Math., Discrete Appl. Math, J. Combin. Optim.，Int. J. Quantum Chem, MATCH等国际重要期刊上发表SCI论文二十余篇; 目前正在主持国家自然科学基金委面上项目一项，主持完成国家自然科学基金委青年基金、数学天元基金和博士后基金一等资助各1项。多次访问美国加州大学戴维斯分校计算机系，合作者为世界著名计算生物学家Dan Gusfield教授。2012年荣获甘肃省自然科学三等奖；2013年荣获甘肃省高等学校青年教师成才奖；2015年荣获兰州大学隆基教学骨干奖。
