Transitive Reduction in Parallel via Branchings

Abstract

This document studies the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. The main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O(n Cubed) processors on a PRAM. The authors' algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. Also presented are sequential algorithms for the problem that run in time O(m+n logn).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1988
Accession Number
ADA200520

Entities

People

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

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Bridges
  • California
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Electronics
  • Illinois
  • Intervals
  • Iterations
  • Observation
  • Parallel Computing
  • Security
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.