An Efficient Distributed Algorithm for Maximum Matching in General Graphs.

Abstract

Let G = (V, E) be a finite, undirected, connected graph with the set of vertices V and the set of edges E. A matching M is a subset that no two edges of M are incident on a common vertex. A maximum matching is a matching of maximum cardinality. This thesis presents an efficient distributed algorithm for finding a maximum matching in a general graph. In designing his distributed matching algorithm, the author is concerned with the communication complexity. The maximum number of message transmissions determines the efficiency of the algorithm. He concentrates on minimizing the number of messages for two reasons. First, in an actual distributed system, the communication time would likely be much greater than the processing time. Second, in commercial computer networks, common carriers often charge by the number of packets or bits rather than by time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA176114

Entities

People

  • Michael C. Wu

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Broadcasting
  • Computational Science
  • Computations
  • Computer Networks
  • Computer Science
  • Computers
  • Engineering
  • Illinois
  • Network Protocols
  • Network Topology
  • Networks
  • Parallel Computing
  • Parallel Processing
  • Preprocessing
  • Topology
  • Universities

Readers

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