No label defined (Q3972951)

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 16298
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 16298

      Statements

      0 references
      26 June 1992
      0 references
      edge disjoint paths
      0 references
      homotopic routing
      0 references
      VLSI design
      0 references
      multicommodity flow
      0 references
      \(T\)-joins
      0 references
      \(T\)-cuts
      0 references
      [For the entire collection see Zbl 0719.00011.] Let \(G=(V,E)\) be a connected graph and \(T\) a subset of \(2k\) vertices arranged in pairs \((s_ i,t_ i)\). Then the disjoint (edge disjoint) paths problem for \(G\) is to determine whether there are \(k\) pairwise disjoint (edge disjoint) \(s_ i-t_ i\) paths, \(1\leq i\leq k\). We abbreviate this to DPP and EDPP, respectively. These problems, especially the EDPP, have gained considerable significance because of their applications to the routing problem in VLSI design. The paper under review is a comprehensive survey of the results, both theoretical and algorithmic, obtained in the solution of these and other closely related problems of graph theory. The presentation is arranged in nine sections which we briefly summarize below. The introductory first section sets up the notations and gives a new proof of Menger's theorem using the submodularity property of the degree function \(d(X)=\) the number of edges \(uv\) with \(u\in X\) and \(v\in V-X\). In the second section the path problems are posed and their algorithmic complexity status is summarized. The given graph \(G=(V,E)\) is called the supply graph and an auxiliary graph \(H=(V,F)\) where \(F=\{s_ it_ i, 1\leq i\leq k\}\) called the demand graph is introduced. \(G+H\) is the superposition of \(G\) and \(H\) and may contain parallel edges. The cut criterion (CC): \(d_ G(X)\geq d_ H(X)\) for all \(X\subseteq V\) is introduced, \(d_ H(X)\) is called the congestion of the cut \(\bigtriangledown(X)=(X,V-X)\) and \(s(x)=d_ G(X)-d_ H(X)\) is called the surplus of \(\bigtriangledown(X)\). The multicommodity flow problem (MCFP) is to assign non-negative weights \(w(e)\) to the edges of \(G\) such that the sum of the weights assigned to \(s_ i-t_ i\) paths is at least one and the sum of the weights assigned to paths passing through any edge is at most one. The distance criterion (DC) is \(\sum \hbox{dist}_ w(u,v): uv\in F)\leq\sum (w(e): e\in F)\), where \(\hbox{dist}_ w(u,v)\) is the smallest \(w\)-weight of a \(u-v\) path in \(G\). It is mentioned how the MCFP has a solution if and only if DC holds for every \(w\in R^ E_ +\), and how the EDPP is a 0-1 solution to the MCFP, so that the latter may be called a fractional solution to the EDPP. The case of directed graphs is also discussed using the directed cut criterion. Section 3 discusses several results giving sufficient conditions on \(G\) and \(H\) which ensure that the CC or the DC is a necessary and sufficient condition for the existence of a solution for EDPP. A typical one is the fundamental result of Seymour: If \(G+H\) is planar and Eulerian then the CC is a necessary and sufficient condition for the solvability of EDPP. The author then poses the challenging problem of finding a unified theorem implying all the planar results so far obtained. Results for MCFP and digraphs as well as dualization in the planar case (which changes cuts to circuits and Eulerian to bipartite) are also discussed. The author starts Section 4 with some results on the non-existence of solutions to the EDPP when \(k=2\). He then discusses some conditions on the disposition of the terminal vertices which are sufficient for some strong cut criterion to ensure the existence of a solution to the EDPP. In Section 5 he discusses the grid graphs which are relevant in the application to VLSI designs. Here the graph \(G\) is a subgraph of the finite subgraph of the grid graph enclosed in a rectangle. A natural cut is a set of horizontal segments lying in a column. A similar row cut can be defined. A concept of parity congestion is defined and the revised cut criterion (RCC) states that the parity congestion of a row or column cannot exceed the surplus. A typical result due to the author is that the EDPP has a solution if and only if the RCC holds for every row or column. A brief mention is also made of the homotopic path problem. In Section 6 the author quotes several known results on the algorithmic complexity of the paths problems under various settings. Included among these is Thomassen's conjecture on graphs \(k\)-lined on edges. In Section 7 he introduces the maximization problem corresponding to the EDPP. This asks for the maximum number \(M\) of edge disjoint paths joining the terminals \(s_ i-t_ i\), \(1\leq i\leq k\), more than one \(s_ i-t_ i\) path being allowed. If \(m_ i\) denotes the maximum cardinality of a cut separating each terminal pair, Rothschild-Whinston's theorem that \(f\) or \(k=2\), if \(d_ G(v)\) is even for each non-terminal node \(v\), then \(m_ 1=M\), is proved. A new proof of a more complicated result of Lomonosov (also for \(k=2\)) is given. Several other results for general \(k\) are also discussed. Section 8 is devoted to a discussion of \(T\)-joins and \(T\)-cuts and their weighted (fractional) versions. Seymour's result that in a bipartite graph the maximum number of disjoint \(T\)-cuts equals the minimum cardinality of a \(T\)-join is mentioned. It is demonstrated that the Edmonds-Johnson algorithm (for the Chinese postman problem) can be used to solve the minimum weight \(T\)-join problem in strongly polynomial time. For the dual problem of finding a maximum packing of \(T\)-cuts, the Barahona-Cunningham algorithm is discussed and a conceptually better algorithm based on an idea of Sebö is presented. Several other results are also discussed. The last Section 9 is devoted to a discussion of packings of cuts and circuits, and starts with the Lucchesi-Younger result: The maximum number of disjoint directed cuts equals the minimum number of edges covering all the cuts. Fractional packings of cuts and circuits are introduced and their relations to the multicommodity flow problem and the EDPP are discussed. Important distinctions between the directed and the undirected cases are brought out. On the whole, this is a very informative and comprehensive review of the topics discussed. However, a wide sprinkling of non-insignificant typographical errors jars smooth reading.
      0 references

      Identifiers

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