#
Minimum s-t cut of a planar undirected network in o(n log^{2}
(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