Minimum S-T Cut of a Planar Undirected Network in O(n log2(n)) Time,

Abstract

We have presented an algorithm for computing a minimum s-t cut of a planar undirected network. Our algorithm runs in an order of magnitude less time than previous algorithms for this problem. An additional attractive feature of this algorithm is its simplicity, as compared to certain other algorithms for computing minimum s-t cuts for sparse networks.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA095539

Entities

People

  • John Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Flow Network
  • Graphs
  • Military Research
  • Parallel Computing
  • Standards
  • Terminals
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.