欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Graph searches on structured families of graphs
时间  Datetime
2017-12-15 11:00 — 12:00 
地点  Venue
Middle Lecture Room
报告人  Speaker
Lalla Mouatadid
单位  Affiliation
University of Toronto
邀请人  Host
Yaokun Wu
报告摘要  Abstract

Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. Some families of graphs have a vertex ordering characterization, and we review how graph searching is used to produce such vertex orderings. These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance).

In this talk, we focus on two graph searches: Lexicographic breadth first search (LexBFS), and Lexicographic depth first search (LexDFS). In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. If time permits, we will discuss the relationship between graph searches and graph convexities.