Using the DFS Algorithm for Finding Long Paths in Random and Pseudo-Random Graphs

Computer Science/Discrete Mathematics Seminar I
Topic:Using the DFS Algorithm for Finding Long Paths in Random and Pseudo-Random Graphs
Speaker:Michael Krivelevich
Affiliation:Tel Aviv University
Date:Monday, September 23
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2013/0923-MichaelKrivelevich

The Depth First Search (DFS) algorithm is one of the most standard graph exploration algorithms, used normally to find the connected components of an input graph. Though perhaps less popular than its sister algorithm, Breadth First Search (BFS), the DFS algorithm is very simple and handy and has many nice properties; it is particularly well suited for finding long paths. In this talk I will discuss how basic properties of the DFS algorithm can be exploited to argue about the (typical) existence of long paths in random and pseudo-random graphs. Based partly on a joint work with Benny Sudakov.