MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Strong Bridges and Strong Articulation Points of Directed Graphs

Giuseppe F. Italiano
University of Rome "Tor Vergata"
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Friday, 25 April 2014
13:00
45 Minutes
E1 4
024
Saarbrücken

Abstract

Given a directed graph G, an edge is a strong bridge if its removal

increases the number of strongly connected components of G. Similarly,
a vertex is a strong articulation point if its removal increases the
number of strongly connected components of G. Strong articulation
points and strong bridges are related to the notion of 2-vertex and
2-edge connectivity of directed graphs, which surprisingly seems to
have been overlooked in the past. In this talk, we survey some very
recent work in this area, both from the theoretical and the practical
viewpoint.

Contact

Sayan Bhattacharya
--email hidden
passcode not visible
logged in users only

Sayan Bhattacharya, 04/07/2014 12:15 -- Created document.