Implementation of an Efficient Algorithm to Detect Maximal Cliques in a Conflict Graph

Abstract

In military operations, radio frequency communications play an important role in command and control. Since the breadth of control may be limited by frequency and channel constraints, research continues to search for better ways to optimize the frequency allocation. In this thesis, graphs are used to model radio communications networks. The problem considered is the detection of maximal cliques, representing subnets, from the graph model. However, detection of cliques is an NP-complete problem. Since NP-complete problems are not likely to be solvable in a reasonable time if the input is large, this paper limits the network input to six stations and fifteen transmissions. An algorithm is implemented in Pascal to detect all maximal cliques of a network and is known as the program CLIQUE. The program is designed to accept arbitrary connected graphs without being affected by isomorphisms and without generating duplicates. This thesis describes a limited solution to the clique problem and solves a subproblem of the communications frequency problem in real time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1990
Accession Number
ADA237181

Entities

People

  • Kristi J. Bell

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Availability
  • Classification
  • Command And Control
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Detection
  • Frequency
  • High Level Languages
  • Military Operations
  • Radio Communications
  • Radio Frequency
  • Schools
  • Security
  • United States

Readers

  • Database Systems and Applications
  • Graph Algorithms and Convex Optimization.
  • Radio communications and signal processing.

Technology Areas

  • Fully Networked C3
  • Fully Networked C3 - Command and Control