Accession Number:

ADA237181

Title:

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

Descriptive Note:

Master's thesis,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1990-06-01

Pagination or Media Count:

130.0

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.

Subject Categories:

  • Computer Programming and Software
  • Radiofrequency Wave Propagation
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE