welcome!欢迎进入兰州大学萃英学院

0931-8913399

当前位置: 本站首页 > 学术科技 > 讲座信息 > 正文

多伦多大学lalla Mouatadid

发布人: 萃英学院办公室浏览量: 发布时间:2017-12-15

应萃英学院邀请,多伦多大学lalla Mouatadid博士来我院作学术报告,欢迎广大师生参加。

报告题目一:Graph searches on structured families of graphs

报告时间: 2017年12月18日上午11:00-12:30

报告题目二:LexDFS and Cocomparability graphs: Independent set - A case study.

报告时间:2017年12月18日下午16:30-18:00

报告地点:观云楼813

报告人:lalla Mouatadid 博士

报告一内容:

Graph searching, a mechanism to traverse a graph visiting one vertex at atime in a specific manner, is a powerful tool used to extract structurefrom various families of graphs. Some families of graphs have a vertexordering characterization, and we review how graph searching is used toproduce such vertex orderings . These orderings expose structure that weexploit to develop efficient linear and near-linear time algorithms forsome NP-hard problems (independent set, colouring, Hamiltonicity forinstance).In this talk, we focus on two graph searches: Lexicographic breadth firstsearch (LexBFS), and Lexicographic depth first search (LexDFS).In particular, we will focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs, and then prove fixed point type theorems for LexBFS. If time permits, we will discuss the relationship between graph searches and graph convexities.

报告二内容:

LexDFS and Cocomparability graphs: Independent set - A case study. Graph searching is a mechanism to traverse a graph visiting one vertex at atime in a specific manner.It is a powerful tool that has led to a number of elegant algorithms. In this talk, we introduce the graph search LexDFS, and will focus on cocomparability graphs, to showcase the power of this graph search on this particular graph family.

萃英学院

2017年12月15日

上一篇:中国传媒大学张晶教授讲座
下一篇:大学生心理压力的调试与积极心理构建

版权所有:兰州大学萃英学院     邮编:730000