Almost-Optimum Parallel Speed-Ups of Algorithms for Bipartite Matching and Related Problems

Abstract

This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. Given is a bipartite graph with n vertices, m edges, and integral edge costs at most N in magnitude. This bound is within a factor of log p of optimum speed-up of the best known sequential algorithm, which in turn is within a factor of log (nN) of the best known bound for the problem without costs (maximum cardinality matching). Extensions of the algorithm are given, including an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). (KR)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 18, 1989
Accession Number
ADA215111

Entities

People

  • Harold N. Gabow
  • Robert Tarjan

Organizations

  • Princeton University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Efficiency
  • Graph Theory
  • Guarantees
  • Integrals
  • Iterations
  • Linear Programming
  • Lists (Data Structures)
  • Logarithm Functions
  • Notation
  • Parallel Computing
  • Parallel Processing
  • Residuals

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research