Implementation of an efficient algorithm to detect maximal cliques in a conflict graph
Loading...
Authors
Bell, Kristi Jo.
Subjects
Maximal clique
conflict graph
algorithm
heuristic
NP-complete
conflict graph
algorithm
heuristic
NP-complete
Advisors
Hefner, Kim A.S.
Date of Issue
1990-06
Date
June 1990
Publisher
Monterey, California: Naval Postgraduate School
Language
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.
Type
Thesis
Description
Series/Report No
Department
Computer Science (CS)
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
viii, 121 p. ill.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
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.