A Graph Theoretic Approach to the Optimal Slot Utilization Problem for Naval Communication Networks

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1992
Accession Number
ADA256143

Entities

People

  • Pamela K. Bell

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Classification
  • Communication Networks
  • Competition
  • Graph Theory
  • Mathematical Models
  • Mathematics
  • Models
  • Networks
  • New York
  • Operations Research
  • Security
  • Social Sciences
  • Transmitters
  • Transmitting
  • United States

Readers

  • Computational Modeling and Simulation
  • Electromagnetic Wave Scattering and Antenna Radiation Engineering
  • Graph Algorithms and Convex Optimization.