Summary
Don't miss this year's 28th Annual Christmas Lecture given by Dr. Donald Knuth!
2024 Talk: Strong Components and Weak Components
A directed graph can often be best understood and used if we partition its vertices into separate components of various kinds. Most important are the strongly connected components, called “strong components” for short; and strong components are in turn partitioned into “weak components.”
Two definitions of weak components have appeared in the literature of graph theory. One of them is rather weak and uninteresting, while the other is becoming more and more relevant and appreciated (see weak components revived). Basically, the strong components are the smallest clusters of vertices that you can shrink to a point and obtain a dag, a digraph with no oriented cycles. The weak components, correctly defined, are the smallest clusters that you can shrink to a point and obtain an oriented path.
Dr. Knuth will discuss Robert Tarjan's beautiful algorithms for computing the strong and weak components of a given directed graph. (This will be fun because Dr. Knuth's personal favorite, among all of the algorithms of all kinds that he has encountered so far in his life, is Tarjan's method for discovering the strong components as it explores the graph.) Furthermore, if time permits, Dr. Knuth disclose the answer to the following riddle: In what major world city are shirts of size XL smaller than shirts of size L?
Please join us at NVIDIA auditorium on campus on Thursday, December 5, 2024 at 5:00 pm or sign up now to receive a link, and reminder to watch via live stream.
- Item 4
