Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs

Thomas A. Feo and J. Scott Provan
Additional contact information
Thomas A. Feo: The University of Texas at Austin, Austin, Texas
J. Scott Provan: University of North Carolina, Chapel Hill, North Carolina

Operations Research, 1993, vol. 41, issue 3, 572-582

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 series and parallel reductions and delta-wye transformations. The method is applied to a class of optimization/equilibnum problems which includes max flow, shortest path, and electrical resistance problems.

Keywords: analysis of algorithms; data structures: efficient structure for solving many types of network problems; networks/graphs; flow algorithms: solves a class of flow equilibrium problems; networks/graphs; theory: reduction method for 2-terminal planar graphs (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.3.572 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:3:p:572-582

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().