Skip to main content
Journal cover image

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

Publication ,  Conference
Reif, JH
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 1981

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540108436

Publication Date

January 1, 1981

Volume

115 LNCS

Start / End Page

56 / 67

Related Subject Headings

  • Artificial Intelligence & Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1981). Minimum s-t cut of a planar undirected network in o(n log2(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
Reif, J. H. “Minimum s-t cut of a planar undirected network in o(n log2(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.
Reif JH. Minimum s-t cut of a planar undirected network in o(n log2(n)) time. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1981. p. 56–67.
Reif, J. H. “Minimum s-t cut of a planar undirected network in o(n log2(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.
Reif JH. Minimum s-t cut of a planar undirected network in o(n log2(n)) time. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1981. p. 56–67.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540108436

Publication Date

January 1, 1981

Volume

115 LNCS

Start / End Page

56 / 67

Related Subject Headings

  • Artificial Intelligence & Image Processing