Parallel Update of Minimum Spanning Trees in Logarithmic Time.

Abstract

Parallel algorithms are presented for updating a minimum spanning tree when the cost of an edge changes or when a new node is inserted in the underlying graph. The machine model used is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described in this paper for updating a minimum spanning tree require O(log n) time and O(n square) processors. These algorithms are efficient when compared to previously known algorithms for initial construction of a minimum spanning tree that require O(log n to the base 2) time and use O(n square) processors.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1984
Accession Number
ADA150497

Entities

People

  • I. V. Ramakrishnan
  • S. Pawagi

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Availability
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Graph Theory
  • Maryland
  • Mathematics
  • Scientific Research
  • Security
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

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