Accession Number:

AD0657428

Title:

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

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE INST OF TECH PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1967-07-01

Pagination or Media Count:

13.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE