×

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
Full Text: DOI