Examining a Subproblem of the Frequency Assignment Problem Using a Conflict Graph

Abstract

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. (Author) (KR)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1990
Accession Number
ADA226677

Entities

People

  • Donald W. Hintze

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies
  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Communication Networks
  • Communication Systems
  • Computer Programming
  • Computer Programs
  • Computers
  • Integer Programming
  • Linear Programming
  • Mathematical Models
  • Mathematical Programming
  • Mathematics
  • Networks
  • Nonlinear Programming
  • Operations Research
  • Optimization
  • United States

Readers

  • Artificial Intelligence
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design