| Title: |
DELTA-WYE TRANSFORMATIONS AND THE EFFICIENT REDUCTION OF TWO-TERMINAL PLANAR GRAPHS. |
| Authors: |
Feo, Thomas A.1; Provan, J. Scott2 |
| Source: |
Operations Research. May/Jun1993, Vol. 41 Issue 3, p572. 11p. 10 Diagrams. |
| Subject Terms: |
*Algorithms; *Graphic methods; *Mathematics; Algebra; Mathematical transformations; Equilibrium; Electric networks |
| Abstract: |
The article presents information on delta-wye transformation (DWR) and the efficient reduction of two-terminal planar graphs. The purpose of this paper is two-fold. First, a new algorithm is given for reducing a planar graph to a single edge using the reductions T1-T6. The algorithm is strikingly simple, relatively easy to prove, and can be applied directly to the graph itself, thus avoiding the problems of grid embeddings. Second, an approach is given for looking at optimization and equilibrium problems which unifies the shortest path, maximum flow, and electrical network problems also mentioned, indicating how more complex related problems can be solved in this context. To conclude the authors mentioned briefly two further uses of the DWR algorithm for solving related problems. The first of these involves the extension of the various equilibrium problems to situations involving more than two terminals. The computational complexity of reducing a connected graph using various operations has also been studied. |
| Database: |
Business Source Premier |