Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, June 13, 2006, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Dominic Meier

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs

By Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan (submitted)

Given a strongly connected directed graph, the paper analyses the complexities for generating two families of subgraphs. There are two main results, the first of which is that all minimal strongly connected subgraphs can be enumerated in incremental polynomial time. On the other side, the second result states that enumerating all minimal directed cuts is NP-hard (given a collection of minimal directed cuts, it is NP-hard to tell whether it is complete). The family of minimal directed cuts is in some sense dual to the family of minimal strongly connected subgraphs.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login