A Parallel Matching Algorithm for Convex Bipartite Graphs and Applications to Scheduling.

Abstract

An efficient parallel algorithm to obtain maximum matching in convex bipartite graphs is obtained. This algorithm can be used to obtain efficient parallel algorithms for several scheduling problems. Some examples are: job scheduling with release times and deadlines; scheduling to minimize maximum completion time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1981
Accession Number
ADA111378

Entities

People

  • Eliezer Dekel
  • Sartaj Sahni

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Equations
  • Instructions
  • Iterations
  • Language
  • Military Research
  • Minnesota
  • Scheduling (Production)
  • Standards
  • Terminals
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Parallel and Distributed Computing.