Parallel (Delta + 1) Coloring of Constant-Degree Graphs,

Abstract

This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of delta in (delta + 1) colors and for finding a maximal independent set in a constant-degree graph. Given a graph with n vertices, the algorithms run in O (lg*n) time on EREW PRAM with O(n) processors. The algorithms use only local communication and achieve the same complexity bounds when implemented in the distributed model of parallel computation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1986
Accession Number
ADA176290

Entities

People

  • Andrew V. Goldberg
  • Serge A. Plotkin

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Governments
  • Identification
  • Iterations
  • Massachusetts
  • Military Research
  • Notation
  • Parallel Computing
  • Procedures (Computers)
  • Standards

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.