Accession Number:

ADA158918

Title:

ARC Colorings, Partial Path Groups, and Parallel Graph Contractions.

Descriptive Note:

Technical rept.,

Corporate Author:

MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH

Personal Author(s):

Report Date:

1985-07-01

Pagination or Media Count:

40.0

Abstract:

This document defines an algebraic structure on the paths in a graph based on a coloring of the arcs. Using this structure, basic classes of graphs trees, hypercubes, arrays, cliques, etc. are characterized by simple algebraic properties. The structure provides a framework for defining parallel contraction operations on a graph, in which many pairs of nodes are simultaneously collapsed into single nodes, but the degree of the graph does not increase. Such operations are useful in defining systematic strategies for simulating large networks of processors by smaller ones, or in building pyramids of networks. Additional keywords Applied mathematics Computer graphics Computer vision and Mesh. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE