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
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references