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

多伦多大学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日

 

                                         

版权所有 兰州大学萃英学院 联系电话:0931-8913399 通讯地址:甘肃省兰州市天水南路222号 邮编:730000
设计制作 宏点网络 备案号申请中