MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
IPCO04.pdf (201.24 KB)
Booktitle*:
Integer programming and combinatorial optimization : 10th International IPCO Conference
Event, URLs
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni
Created
02/23/2005 02:37:05 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Christine Kiesel
Khaled Elbassioni

Edit Dates
02.05.2007 15:39:26
21.04.2005 16:27:26
02/23/2005 02:37:05 PM


File Attachment Icon
IPCO04.pdf