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.
RightsThis 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.
Showing items related by title, author, creator and subject.
Bekatoros, Nikolaos (2010-06);In today’s information age teams reside in multi-participant problem solving processes that operate within both the physical and virtual environment (Gibson & Cohen, 2003). Teams in order to collaborate form their own ...
Gera, Ralucca; Rasmussen, Craig W.; Horton, Steve (2006);Given a graph G, the dominator coloring problem seeks a proper coloring of G with the additional property that every vertex in the graph dominates an entire color class. The safe clique partition problem seeks a partition ...
Gergen, Kenneth J.; McNamee, Sheila; Barrett, Frank (2001);Most of us feel more comfortable in certain groups than others, and indeed find certain people just plain wrong headed or evil - perhaps neo-Nazis, the KKK, the Mafia, terrorist groups. This sense of alterity - distance ...