运筹学与控制论组学术报告

题 目：A Vertex Ordering Characterization of Asteroidal
Triple-free (AT-free) Graphs

报告人：Professor Derek G. Corneil
Department of Computer Science
University of Toronto,Canada

时 间：2011年4月12日 上午10:00-10:50

地 点：华东师大闵行校区数学系102报告厅

报告内容简介：Many families of graphs have a vertex ordering characterization that plays an important role
in various algorithms (often based on graph searching) for graphs in the family. Examples
include unit inverval graphs, interval graphs, and cocomparability graphs. Note that an asteroidal
triple is an independent triple of vertices, S, such that between any two vertices in S there is a path
that avoids the neighbourhood of the third vertex in S. AT-free graphs strictly contain the families
of graphs mentioned above, and it has long been questioned whether AT-free graphs also have
such a characterization. An early attempt to solve the problem lead to the discovery of path-orderable graphs, a family that lies strictly between cocomparability graphs and AT-free graphs.
This talk presents a recent vertex ordering characterization of AT-free graphs;
note that similar characterizations hold for graphs of bounded asteroid number.
The talk concludes with open questions, especially pertaining to the search for graph search
based algorithms for AT-free graphs.
[Joint work with Juraj Stacho]