MPI-INF D1 Publications: Proceedings Article: Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2013) | last year (2012) | two years ago (2011) | Notes URL

Action:

Options:

Goto entry point

Author, Editor

Author(s):

Boros, Endre
Elbassioni, Khaled M.
Gurvich, Vladimir
Khachiyan, Leonid

dblp
dblp
dblp
dblp

Not MPG Author(s):

Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid

Editor(s):

Bienstock, Daniel
Nemhauser, George

dblp
dblp

Not MPII Editor(s):

George L. Nemhauser,
Daniel Bienstock

BibTeX cite key*:

Elbassioni2004e

Title, Booktitle

Title*:	Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
Attachment(s):	IPCO04.pdf (201.24 KB)
Booktitle*:	Integer programming and combinatorial optimization : 10th International IPCO Conference

Event, URLs

URL of the conference:
URL for downloading the paper:
Event Address*:	New York, NY, USA	Language:	English
Event Date* (no longer used):		Organization:
Event Start Date:	7 June 2004	Event End Date:	11 June 2004

Publisher

Name*:	Springer	URL:
Address*:	Berlin, Germany	Type:

Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:	3064	Number:
Month:	June	Pages:	152-162
Year*:	2004	VG Wort Pages:
ISBN/ISSN:	3-540-22113-1	Sequence Number:
DOI:


(LaTeX) Abstract:	We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-complete to tell whether it can be extended. The latter result implies, in particular, that for a given set of points , it is NP-hard to generate all maximal subsets of contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem.


Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Elbassioni2004e,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Gurvich, Vladimir and Khachiyan, Leonid},
EDITOR = {Bienstock, Daniel and Nemhauser, George},
TITLE = {Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems},
BOOKTITLE = {Integer programming and combinatorial optimization : 10th International IPCO Conference},
PUBLISHER = {Springer},
YEAR = {2004},
VOLUME = {3064},
PAGES = {152--162},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {New York, NY, USA},
MONTH = {June},
ISBN = {3-540-22113-1},
}

Entry last modified by Christine Kiesel, 05/02/2007

Edit History (please click the blue arrow to see the details)

Attachment Section

View attachments here:

IPCO04.pdf

IPCO04.pdf