Cellular D-Graph Automata with Augmented Memory.

Abstract

This paper deals with cellular d-graph automata in which each node has internal memory proportional to log sub d-1 of N where N is the number of nodes in the underlying graph G. It is shown how such an automation can assign unique labels to the nodes of G in O(log sub d-1 of N) time. Such an automation can also count the number of nodes and edges in G in O(log sub d-1 of N) time. Algorithms for identifying all the cut nodes and all bridges in G, each in O(log sub d-1 of N) time, are also presented. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1979
Accession Number
ADA077389

Entities

People

  • Angela Wu
  • Tsvi Dubitzki

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Automata
  • Computations
  • Computer Science
  • Computers
  • Maryland
  • Mathematics
  • Recognition
  • Scientific Research
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Robotics and Automation.