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) : Moyles,Dennis M. ; Thompson,Gerald L.

Report Date : JUL 1967

Pagination or Media Count : 13

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)

Descriptors :   (*ALGORITHMS, *GRAPHICS), (*NUMERICAL ANALYSIS, SEQUENCES(MATHEMATICS)), THEOREMS, SET THEORY, MATRICES(MATHEMATICS), PROBLEM SOLVING, MATHEMATICAL LOGIC, OPERATIONS RESEARCH, SEQUENTIAL ANALYSIS, MATHEMATICS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE