ALEA Days / Journées ALEA

Collection ALEA Days / Journées ALEA

Organizer(s) Chapuy, Guillaume ; Goldschmidt, Christina ; Duchi, Enrica
Date(s) 3/18/19 - 3/22/19
linked URL
00:00:00 / 00:00:00
13 24

New perspectives for graph searches on structured families of graphs

By Michel Habib

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. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS). Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently 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) on some special classes of graphs such as cocomparability graphs. 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. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids. These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider. To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.19374303
  • Cite this video Habib Michel (3/14/18). New perspectives for graph searches on structured families of graphs. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19374303
  • URL

Last related questions on MathOverflow

You have to connect your account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback