No label defined (Q4664045)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2152473
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2152473 |
Statements
5 April 2005
0 references
graph algorithm
0 references
Arc connectivity
0 references
location problem
0 references
Network flow
0 references
deficient set
0 references
tree hypergraph
0 references
0.8533742427825928
0 references
0.8452605605125427
0 references
0.8397639989852905
0 references
0.839523434638977
0 references
0.839523434638977
0 references
A polynomial time algorithm, based on minimum transversal of a tree hypergraph, is obtained for finding a minimum cardinality vertex set in an edge-capacitated directed graph which allows inflows from and outflows to any vertex of at least given fixed respective amounts. Extensions of the problem to varying amounts of demand/supply on the vertices, or varying vertex costs (even with equal inflow and outflow bounds) are all shown to be NP-hard.
0 references
