Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related 
Geometric Problems

Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid; Bienstock, Daniel; Nemhauser, George

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems

MPS-Authors

/persons/resource/persons44374

Elbassioni, Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Boros, E., Elbassioni, K., Gurvich, V., & Khachiyan, L. (2004). Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems. In Integer programming and combinatorial optimization: 10th International IPCO Conference (pp. 152-162). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-291E-2

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.