DELTA-WYE TRANSFORMATIONS AND THE EFFICIENT REDUCTION OF 2-TERMINAL PLANAR GRAPHS
成果类型：
Article
署名作者：
FEO, TA; PROVAN, JS
署名单位：
University of North Carolina; University of North Carolina Chapel Hill
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.3.572
发表日期：
1993
页码：
572-582
关键词：
摘要：
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.