Fast and Processor-Efficient Parallel Algorithms for Reducible Flow Graphs

Abstract

This document presents parallel NC algorithms for recognizing reducible flow graphs, and for finding dominators, minimum feedback vertex sets, and a depth first search numbering in an rfg. All of these algorithms run in polylog parallel time using M (n) processors, where M (n) is the number of processors needed to multiply two nxn matrices in polylog time; this is the best processor bound currently known for polylog-time parallel algorithms for directed graphs. It is shown that finding a minimum feedback vertex is in vertex-weighted rfg's or finding a minimum feedback arc set in arc-weighted rfg's is complete. For arc or vertex weights in unary, we present RNC algorithms for these problems and show that these problems are in NC if and only if the problem of finding a maximum matching is in NC. Keywords: Parallel computations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1988
Accession Number
ADA201651

Entities

People

  • Vijaya Ramachandran

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Feedback
  • Flow Network
  • Graphs
  • Lists (Data Structures)
  • Military Research
  • New York
  • Notation
  • Parallel Computing
  • Polynomials
  • Sequences
  • Standards

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.