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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1985
Accession Number
ADA158918

Entities

People

  • Azriel Rosenfeld

Organizations

  • University of Maryland

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Applied Mathematics
  • Artificial Intelligence
  • Collapse
  • Computations
  • Computer Graphics
  • Computer Science
  • Contracts
  • Generators
  • Geometry
  • Image Processing
  • Mathematics
  • Sequences
  • Simulations
  • Two Dimensional
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms