ON PARTITIONING AN ARBITRARILY GIVEN SET OF ELEMENTS OF A FINITE BOOLEAN ALGEBRA INTO THE MINIMUM NUMBER OF SETS OF COMPATIBLE ELEMENTS.

Abstract

A mathematical model for a simplified version of a time schedule for classes was devised and studied. An explanation of the problem in terms of Boolean algebra is presented. The problem is restated in terms of graph theory, showing that the problem is the same as that of finding the chromatic number of a given graph. An attempt is made to gain insight into a solution of this problem by studying all graphs of order six and less, which are tabulated along with certain of their attributes. Random graphs of higher order are then studied. The digital computer is used to find the number of complete subgraphs of every order within each graph examined.

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1964
Accession Number
AD0481271

Entities

People

  • Samuel C. Colwell Iii.

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Boolean Algebra
  • Computers
  • Computing Devices
  • Digital Computers
  • Graph Theory
  • Mathematical Models
  • Mathematics
  • Models

Fields of Study

  • Mathematics

Readers

  • Computer Science.
  • Graph Algorithms and Convex Optimization.
  • Theoretical Analysis.