Implementation of an efficient algorithm to detect maximal cliques in a conflict graph
Bell, Kristi Jo.
Hefner, Kim A.S.
MetadataShow full item record
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.
Approved for public release; distribution is unlimited.
Showing items related by title, author, creator and subject.
Luna, Lauro (Monterey, California. Naval Postgraduate School, 2008-03);The Department of Defense (DOD) has placed great emphasis on the networking and connectivity of forces over the last several years. Programs include the Global Information Grid (GIG), Force Net, and Net Centric Warfare to ...
Laflam, David W. (Monterey, California. Naval Postgraduate School, 2000-09);The military is heavily reliant on the transfer of information among various networks in day-to-day operations. Radio-based communications networks that support this volume of information are complex, difficult to manage, ...
Cantrell, Mark E. (Monterey, California. Naval Postgraduate School, 1996-06);Speaker-independent automatic speech recognition (ASR) is a problem of long-standing interest to the Department of Defense. Unfortunately, existing systems are still too limited in capability for many military purposes. ...