Examining a subproblem of the frequency assignment problem using a conflict graph
Hintze, Donald W.
Hefner, Kim A.S.
Thornton, John R.
MetadataShow full item record
There are many problems associated with communication networks. One of the more familiar ones is the frequency assignment problem. Many approaches and techniques have been used in the past in an attempt to solve this problem. This thesis examines a subproblem of the frequency assignment problem, which aids the decision-maker in placing additional links in a network, once a frequency assignment is found. Given a conflict graph for a communications network, the problem involves finding the maximum number of arcs in the corresponding digraph. This digraph is a worst case model for the actual network and will show which additional links may be added to the network in order to enhance communication capabilities. An algorithm was developed to help solve this problem after lower and upper bounds were established for its optimal solution. The algorithm obtains a solution which falls within the bounds and achieves the bounds in special cases.
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.
Bell, Kristi Jo. (Monterey, California: Naval Postgraduate School, 1990-06);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 ...
Vossen, Thomas W.M.; Wood, R. Kevin; Newman, Alexandra M. (Informs, 2016);The open-pit mine block sequencing problem (OPBS) models a deposit of ore and surrounding material near the Earth’s surface as a three-dimensional grid of blocks. A solution in discretized time identifies a profit-maximizing ...
Simplicial with truncated Dantzig-Wolfe decomposition for nonlinear multicommodity network flow problems with side constraints Lawphongpanich, Siriphong (2000);The simplicial decomposition (SD) subproblem for a nonlinear multicommodity network ow problem is simply its linear approximation. Instead of solving the subproblem optimally, this paper demonstrates that performing one ...