AN ALGORITHM FOR FINDING A MINIMUM EQUIVALENT GRAPH OF A DIGRAPH.

Abstract

A directed graph or digraph can be thought of as a communication network among a set of persons, where the vertices of the graph correspond to persons and edges of the graph to directed channels of communication from one person to another. A person is said to be able to 'reach' another if he can send a message to that person. The present paper gives an algorithm for finding the maximum number of edges that can be removed from a digraph without affecting its reachability properties. (Author)

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1967
Accession Number
AD0657428

Entities

People

  • Dennis M. Moyles
  • Gerald L. Thompson

Organizations

  • Carnegie Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Rehabilitation and Prosthetic Care for Military Service Members and Veterans with Limb Loss or Disability.