DELTA-WYE TRANSFORMATIONS AND THE EFFICIENT REDUCTION OF 2-TERMINAL PLANAR GRAPHS

Authors
FEO TA PROVAN JS
Citation
Ta. Feo et Js. Provan, DELTA-WYE TRANSFORMATIONS AND THE EFFICIENT REDUCTION OF 2-TERMINAL PLANAR GRAPHS, Operations research, 41(3), 1993, pp. 572-582
Citations number
20
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
41
Issue
3
Year of publication
1993
Pages
572 - 582
Database
ISI
SICI code
0030-364X(1993)41:3<572:DTATER>2.0.ZU;2-R
Abstract
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 se ries and parallel reductions and delta-wye transformations. The method is applied to a class of optimization/equilibrium problems which incl udes max flow, shortest path. and electrical resistance problems.