Publications [#330508] of John H. Reif

Conference articles PUBLISHED

1. Reif, JH, Minimum s-t cut of a planar undirected network in o(n log2(n)) time, edited by Shimon Even and Oded Kariv, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 115 LNCS (January, 1981), pp. 56-67, Springer Berlin Heidelberg, ISBN 9783540108436 [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge's cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time O(n log²(n)) time on a (uniform cost criteria) RAM. For the case L contains only integers ≤n⁰⁽¹⁾, the algorithm runs in time O(n log(n)loglog(n)). Our algorithm also constructs a minimum s-t cut of a planar graph (i.e., for the case L= {1}) in time O(n log(n)). The fastest previous algorithm for computing a minimum s-t cut of a planar undirected network [Gomory and Hu, 1961] and [Itai and Shiloach, 1979] has time O(n² log(n)) and the best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert, and Saxton, 1977] was O(n²).