Delta-wye transformations and the efficient reduction of two-terminal planar graphs. (English) Zbl 0784.90095
Summary: A simple, \(O(| V|^ 2)\) time algorithm is presented that reduces a connected two-terminal, undirected, planar graph to a single edge, by way of series and parallel reductions and delta-wye transformations. The method is applied to a class of optimization/equilibrium problems which includes max flow, shortest path, and electrical resistance problems.
MSC:
90C35 | Programming involving graphs or networks |
90B10 | Deterministic network models in operations research |
05C85 | Graph algorithms (graph-theoretic aspects) |
90-08 | Computational methods for problems pertaining to operations research and mathematical programming |