Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








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

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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
IPCO04.pdf