A graph theoretic approach to the optimal slot utilization problem for naval communication networks

Download
Author
Bell, Pamela K.
Date
1992-06Advisor
Rasmussen, Craig W.
Second Reader
Thornton, John R.
Metadata
Show full item recordAbstract
This paper approaches the optimal slot utilization problem in a Naval Battle Group by modelling ships capable of transmitting on a particular frequency as vertices in a graph, and the relationships between them as edges in that graph. We then analyze the structure of the resultant graph and find an upper bound on the chromatic number of its conflict graph to take into account all possible patterns of interference in determining the minimum number of time slots required, thereby allowing efficient and effective net throughput. Our results include the identification of specific types of graphs in which an exact solution is possible based upon the maximum degree of all vertices in the graph, as well as an algorithm for general graphs which will identify an upper bound on the chromatic number of their conflict graph. Original results are proven, and analysis and examples of the algorithm are provided.
Rights
This 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.Collections
Related items
Showing items related by title, author, creator and subject.
-
The minimization of multiple valued logic expressions using parallel processors
Oral, Sabri Onur (Monterey, California. Naval Postgraduate School, 1991-09);The process of finding an exact minimization for a multiple-valued logic (MVL) expression requires an extensive search and enormous computation time. One of the heuristics to reduce this computation time is the Neighborhood ... -
Implementation of a multi-robot coverage algorithm on a two-dimensional, grid-based environment
Huang, Jo-Wen (Monterey, California: Naval Postgraduate School, 2017-06);With the development and advancement in the technology of control and multi-robot systems, robot agents are likely to take over mine countermeasure (MCM) missions one day. The path planning coverage algorithm is an essential ... -
Expeditionary Mine Countermeasures (ExMCM) C4I Requirements (Continuation)
Das, Arijit (Monterey, California: Naval Postgraduate SchoolMonterey, California. Naval Postgraduate School, 2019-12); NPS-19-N065-AThe ExMCM is a broad program providing an innovative approach to the Mine Warfare mission area, required to operate with both U.S Navy and U.S. Marine Corps forces. The large number of sonar imagery files (from the MK18 ...