## Minimum s-t cut of a planar undirected network in o(n log^{2}(n)) time

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).

### Duke Scholars

##### Altmetric Attention Stats

##### Dimensions Citation Stats

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences

### Citation

^{2}(n)) time. In

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(Vol. 115 LNCS, pp. 56–67). https://doi.org/10.1007/3-540-10843-2_5

^{2}(n)) time.” In

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, 115 LNCS:56–67, 1981. https://doi.org/10.1007/3-540-10843-2_5.

^{2}(n)) time. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1981. p. 56–67.

^{2}(n)) time.”

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 115 LNCS, 1981, pp. 56–67.

*Scopus*, doi:10.1007/3-540-10843-2_5.

^{2}(n)) time. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1981. p. 56–67.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences