报告题目一：Graph searches on structured families of graphs
报告题目二：LexDFS and Cocomparability graphs: Independent set - A case study.
报告人：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.