Minimum s-t cut of a planar undirected network in o(n log2 (n)) time

Published

Conference Paper

© 1981, Springer-Verlag. 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 log2(n)) time on a (uniform cost criteria) RAM. For the case L contains only integers ≤n0(1), 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(n2 log(n)) and the best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert, and Saxton, 1977] was O(n2).

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • January 1, 1981

Published In

Volume / Issue

  • 115 LNCS /

Start / End Page

  • 56 - 67

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540108436

Digital Object Identifier (DOI)

  • 10.1007/3-540-10843-2_5

Citation Source

  • Scopus