Some Generalized Max-Flow Min-Cut Problems in the Plane (Q3978618)
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 12565
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some Generalized Max-Flow Min-Cut Problems in the Plane |
scientific article; zbMATH DE number 12565 |
Statements
Some Generalized Max-Flow Min-Cut Problems in the Plane (English)
0 references
25 June 1992
0 references
max-flow min-cut
0 references
polynomial algorithm
0 references
\(\mathcal NP\)-completeness
0 references
network survivability
0 references
damages
0 references
planar graph
0 references
min-break problem
0 references
max linkage problem
0 references
0.7651649713516235
0 references
0.7627958059310913
0 references
0.7608855366706848
0 references
The paper is motivated by questions of network survivability in the case of damages. Let \(G\) be a planar graph with source \(s\) and sink \(t\) and a finite set of holes, i.e. subsets of the plane homeomorphic to open discs. A minimal subset of holes that disconnects \(s\) from \(t\) is called a break. When each hole is given a nonnegative weight the min-break problem asks for a minimum weight disconnection of \(s\) from \(t\). It is shown that the weighted problem in a directed graph can be solved in polynomial time. Moreover, let a linkage be a collection of \(s-t\) paths so that the number of paths that intersect any given hole does not exceed the weight of the hole. The dual of the min-break problem is finding a maximum linkage. The max linkage problem is shown to be \(\mathcal NP\)-hard. Let \(\tau\) be the minimum cardinality of a break and \(\nu\) the maximum cardinality of a linkage. If \(G\) is undirected, then \(\tau\leq 2\nu+2\) in the unweighted case and \(\tau\leq 8\nu\) in the weighted case. Special cases are described where \(\tau=\nu\) holds. Further variants of the problem (other form of holes, \(G\) not planar, infinite family of holes) are shortly discussed.
0 references