Higher connectivity for directed graphs
Name:
Giuseppe F. Italiano
Affiliation:
Luiss University
Host: 박근수 교수
Date: 8/22/2025 오전 11:00 - 오후 01:00
Location: 302동 551-4호
Summary
Let 𝐺 be a directed graph with 𝑚 edges and 𝑛 vertices. We present s linear-time algorithm for computing the 2-edge-, 2-vertex- and 3-edge-connected components of 𝐺. The new result on 3-edge connectivity is based on a novel characterization of 2-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and 2-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016].
Speaker Introduction
Giuseppe F. Italiano is Professor of Computer Science and Deputy Rector of Artificial Intelligence and Digital Skills at Luiss University, where is also Co-Director of the Master in Artificial Intelligence, the Master in Cybersecurity and the Master in Big Data and Management at Luiss Business School. He has been Visiting Professor in several international universities, including Columbia University, Université Paris-Sud, Max–Planck–Institut fur Informatik, Saarbrücken, Hong Kong University of Science & Technology. He was also Visiting Scientist at AT&T Research Labs and Microsoft Research. He published over 300 articles in international venues and is President of the European Association for Theoretical Computer Science (EATCS).