ARC Colorings, Partial Path Groups, and Parallel Graph Contractions.
MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH
Pagination or Media Count:
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
- Theoretical Mathematics