On partitioning an arbitrarily given set of elements of a finite Boolean algebra into the minimum number of sets of compatible elements
Colwell, Samuel C., III
Church, W. Randolph
MetadataShow full item record
During the past several years at the United States Naval Postgraduate School there has been much interest in obtaining an efficient method for making a time schedule for classes. A mathematical model for a simplified version of this scheduling problem was devised by several faculty members, and this paper is a study of this model. This paper, while not offering a general solution to the simplified scheduling problem, does provide insight into the problem and suggests areas for future study that may lead to a general solution. The paper is presented in four parts, the first being an explanation of the problem in terms of Boolean algebra. The second part restates the problem in terms of graph theory, showing that this problem is the same as the problem of finding the chromatic number of a given graph. The third part is an attempt to gain insight into a solution of this problem by an exhaustive study of all graphs of order six and less, which are tabulated along with certain of their attributes. The fourth part is a study of certain random graphs of higher order. Among other things this study uses the digital computer to find the number of complete subgraphs of every order within each graph examined
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Agrawal, B.N. (1993);This paper presents a boundary-layer model to predict dynamic characteristics of liquid motion in partially filled tanks of a spinning spacecraft. The solution is obtained by solving three boundary-value problems: an ...
Schwartz, Victor Scott (Monterey, California. Naval Postgraduate School, 1998-09-01);A dynamic platform-independent solver is developed for use with network and graph algorithms of operations research. This solver allows analysts to solve a large variety of problems without writing code. Algorithms from a ...
Bothwell, Brian P. (Monterey, California. Naval Postgraduate School, 1990-03);Cumulative search-evasion games (CSEGs) involve two players, a searcher and an evader, who move among some finite set of cells. Neither player is aware of the other player's position during any stage of the game. When the ...