Transitive Reduction in Parallel via Branchings

Abstract

We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O(n cubed) processors on a PRAM. Our algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. We also present sequential algorithms for the problem that run in time O(m+n.logn). (KR)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 15, 1988
Accession Number
ADA215108

Entities

People

  • Danny Soroker
  • Phillip Gibbons
  • Richard Karp
  • Robert Tarjan
  • Vijaya Remachandran

Organizations

  • Princeton University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Bridges
  • Computations
  • Computer Science
  • Computers
  • Intervals
  • Iterations
  • Mathematics
  • New York
  • Observation
  • Parallel Computing
  • Sequences
  • Theoretical Computer Science
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.