DETERMINING PARTITION ELEMENTS WITH FEEDBACK CONSTRAINTS.

Abstract

The partition problem is that step in the layout problem in which it must be decided which of the elementary digital circuits are to be coalesced into a single, electronic package. A solution of the partition problem must satisfy constraints on the maximum number of elementary circuits that can be put into a single package, and on the number of external connections that can be attached to the package. A solution due to Lawler et al, which minimizes delay caused by clustering electronic elements, is extended to cyclic networks. A new algorithm to extract from a graph the maximal strongly-connected subgraphs (lobes) is developed, and a new approach to clustering the digital elements of a lobe is presented. The digital circuit is represented by a bipartite graph, and solutions are expressed in terms of graph theory. (Author)

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1970
Accession Number
AD0709910

Entities

People

  • Thomas Joseph Breckon

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Circuits
  • Clustering
  • Digital Circuits
  • Feedback
  • Graph Theory
  • Mathematics
  • Networks

Readers

  • Computer Science.
  • Graph Algorithms and Convex Optimization.
  • Phased Array Antenna Design.

Technology Areas

  • Microelectronics