IEEE,OF THE

PROCEEDINGS VOL. 68, NO. 12, DECEMBER

1497 1980

Frequency Assignment: Theory and Applications

WILLIAM K. HALE

Absimct-In this paper we introduce theminimum+rder approach to by an assignment is the objective function to be minimized,
frequency.assignment and present a t h e o y which d a t e s this approach and instead of eliminating unwanted interference, conditions
to the traditional one. Thip new approach is potentially more desirable which place acceptable upper bounds upon interference are
than the traditional one. We model assignmentproblems as both
frequencydistance constrained and frequency constrained optimization included amongtheconstraints which an assignment must
problems. The frequencyconstrainedapproachshould be avoided if satisfy. This approach also calls for an ongoing evaluation of
distance separation is employed t o mitigate interference. A restricted thesystem (e.g., theconstraints,conventions, regulations,
dass of graphs, called disk graphs, plays a central role in frequency- policies, and procedures) that governs the way in which the
distanceconstrainedproblems. We introduce two generalizations of
chromatic number and show that many frequency assignment problems spectrum is allocated, assigned, and used. In addition,the
are equivalent to genemlized graph coloring problems. Using these governing system may be modified if it can be demonstrated
equivalences and recentresultsconcerning thecomplexityof graph thatsuch modificationslead to spectrum savings andthat
coloring, we clnssity many frequency assignment problems accordingto existing conditions (e.g., technologic, methodologic, and
the “execution time efficiency“ of algorithms that may be devised for
their solution. We discuss applications to important real world prob-
economic) make such actions feasible. This paper will provide
lems and identify areas for hrther work. tools for quantifying the effects on efficient spectrum use of
such modifications tothe governing system.Forexample,
I . INTRODUCTION suppose that improvements in UHF-TV receivers allow for the
relaxation of some of the UHF taboos. One can use the tools

IF REQUENCY assignment problems arise in a wide variety

of real world situations. Many may be modeled as opti-
mizationproblems having the following form: Given a
collection of radio transmitters to be assigned operating fre-
developed here to determine which taboo(s) to modify for the
maximum gain in spectrum efficiency.
It is misleading to suggest that frequency assignment prob-
lems have alwaysbeenformallymodeled as optimization
quencies, fiid an assignment that satisfies various constraints
and that minimizes the value of a given objective function. problems. In fact, investigations of formal mathematical
Informalmethods, which attempt to findsuch assignments, models of assignment problems did not appear in the literature
have been in use since the beginning of the twentieth century until the 1960’s (e.g., [3], [4]). These earlymodels seem to
when maritime applications of Marconi’s wireless telegraph have enjoyed very limited application and together with other
first appeared [ 11. frequency assignment models in existence as of 1968, were not
The first frequency assignment problems arose fromthe very well known,understoodor acceptedby thespectrum
discovery that transmitters, assigned to the same or to closely utilization experts of that day. As evidence for this conclusion,
related frequencies, had the potential to interfere with one an- consider that the exhaustive report on spectrum engineering
other. Thus the first approach to frequency assignment was to [2] mentions only two frequency assignment models and de-
minimize or eliminate this potential interference (i.e., poten- scribes neither of these.
tial interference was the first objective function). In this ap- Since 1968,theinterestinformalfrequency assignment
proach, the major constraints were the operating bandwidth models has increased significantly as evidenced by the articles
of the transmitters, the band of the electromagnetic spectrum that have appeared in the literature [ 51-[ 181. In addition, as
which the transmitters were capable of using, and, combining early as 1975, one of these approaches had been demonstrated
these two, the total numberof frequencies available for assign- to outperform older frequency assignment procedures on an
ment to the transmitters (under the assumption that frequen- important real world problem [ 131. In spite of these develop-
cies should be assigned to discrete, evenly spaced points in a ments, many policy makers, spectrum managers, and frequency
dedicated portion of the spectrum). A simple way to minimize assigners remain unconvinced that formal models are a viable
interference was to assign different transmitters to different approach tothe wide range of assignment problems which
noninterfering frequencies or to come as close to this as was arise in the real world. (Forexample, a 1977 encyclopedia
possible within theconstraints. Such an approach to fre- volume [ 11, devoted tospectrum management techniques,
quency assignment tied up a lot of the spectrum but remained does not mention a single formal frequency assignment model.)
viable so long as the growth of the usable spectrum kept pace The reasons for this skepticism are clear. First of all, the exist-
with the growth in demandplaced upon it. . ing formal models can handle only a limited range of the wide
Recently (1950-1980), the growth of the usable spectrum variety of real world problems. Forexample,theapproach
has slowed while the demand placed upon it has grown expo- applied in [ 131 obtains significant spectrum savings over older
nentially [ 21. This turn of eventshas inducedspectrum methods when the only interference limiting constraints are
managers t o consider different approaches to frequency assign- cochannel constraints. However, if adjacent channel con-
ment. in one such approach, the amount of spectrum tied up straints are also considered, then these spectrum savings go to
zero as the ratio of adjacent channel to cochannel constraints
Manuscript received May 6, 198O;revised July 25, 1980.
increases. There is an even more important reason for skepti-
The author is withtheITS/NTIA, U.S. Department of Commerce, cism: there exists no unifying theory which demonstrates that
Boulder, CO 80302. formal models are a viable approach to the wide range of prob-

U.S. Government work not protected by U.S. copyright

1498 PROCEEDINGS OF THE IEEE, VOL. 68, NO. 12, DECEMBER 1980

lems which arise in the real world. The purpose of this paper is both frequency and distance separation to mitigate interfer-
to provide such a unifying theory for a wide variety of real ence and are called frequency-distance (F*D) constraints. An
world problems. assignmentprobleminwhich theinterference limitingcon-
Recent developments in the theory of computational com- straints are all F*D constraints is called a frequency-distance
plexity [ 191-[22] allow for the classification of optimization constrained assignment problem, The paper [ 821 discusses the
problems according to the “execution timeefficiency” of algo- origin and application of an elaborate set of F*D constraints
rithms that may be devised for their solution. For example, called the UHF-TV taboos. Asecond type of interference
the book [23] classifies well over 1000 combinatorial prob- limiting constraint specifies that certain combinations of as-
lems but nota single frequency assignment problem is included. signments areforbiddenfor a given pair of transmitters.
An important feature of the theory developed here is that, for Superficially at least such constraints employ only frequency
the first time, many frequency assignment problems are classi- separation to mitigate interferenceand are called frequency
fied according to their complexity. ( F ) constraints. An assignment problem in which the interfer-
Graphcoloring is perhaps the most famousoptimization ence limiting constraints are all frequency constraints is called
problem (e.g., the four-color theorem). That this problem also a frequencyconstrainedassignmentproblem. The papers
is one of the most intensively investigated and applied optimi- [ l o ] , [ 181 investigate such problems.
zationproblems is dramatically evidenced by thenumerous We have mentioned that anassignment should not needlessly
books and articles that have appearedin the literature (e.g., tie up spectrum. Traditionally, thishas meant that the span of
[25]-[81]). Asecond importantfeature of thetheory de- an assignment for a given set of transmitters mustbe mini-
veloped here is that a very close connection is established be- mized (where the span of an assignment is the largest frequency
tween each of the frequencyassignment problems of this paper assigned to a transmitter in theset minus the smallest fre-
and graph coloring. Among the obvious benefits of this con- quency assigned to a transmitter in the set). An assignment
nection is the potential application of well-known graph color- problem in which our objective is to minimize the span of an
ing algorithms and/or heuristics tofrequency assignment assignment is called a minimum span assignment problem. The
problems. Graph colorers will be interested to know that the papers [ 91,[ 131, [ 171, [ 181 investigate such problems.
theory of frequency assignment opensup new vistas in Can minimum
a span assignment waste spectrum?The
chromatic graph theory. Real world problemsnow make it answer is yes for channel assignment problems with interfer-
important to f i d algorithms and/or heuristics for both classi- encelimiting constraintsotherthan cochannel constraints.
cal and generalized graph coloring problems. That is, for such problems it is not uncommon for a minimum
This paper is written primarily for spectrum planners, spec- span assignment to assign transmitters to morefrequencies
trum managers, and frequency assigners. We hope it will also than doesasecond assignment which may or may not bea
be read byoperations researchers, computer scientists and minimumspanassignment. In fact,formanycommon in-
applied mathematicians. The mathematical (Le., graph theory, stances of assignment problems it is impossible to finda
optimizationtheory,complexitytheory) and thespectrum minimum span assignment which actually uses the minimum
engineering backgrounds of members of this audienceare number of frequencies required. (See Examples One and Two
likely to range all over the scale. Forthis reason, we have in Section I11 for details). This potentially useful phenomenon
attemptedto providemotivation forformaldefinitions, de- makes itimportant to formalizea new type of assignment
scribe the meanings of theorems,and to illustrateconcepts problem. Thenumber of frequencies thatan assignment
with examples. We have proved theorems in their least general actually uses is called its order and an assignment problem in
(but most understandable) form,while only stating or mention- which our objective is to minimize the span of an assignment
ing more general theorems which have the same proof. subject to the additional constraint that its orderis minimized
In this paper,a frequency assignment is a function which is called a minimum-order assignment problem.
assigns to each member of a set of transmitters an operating In Section 11,we set down our conventions, notations, and
frequency from a set of available frequencies. Therefore, if A other preliminary definitions. In Section 111,we develop the
is an assignment for the set of transmitters V and if u is a elementary theory of frequency-distance constrained channel
transmitter belonging to V , then A(u) denotes the frequency assignment problems (both minimumspan and minimum
assigned to u by A . In a typical frequencyassignment problem, order). SectionIVpresentsa parallel development forthe
one attempts to find a frequency assignment (i.e., a function more general frequency constrained channel assignment prob-
from a given set of transmitters intoa given set of frequencies) lems. Section V presents other more complicated assignment
that satisfies certain constraints (e.g., a collection of interfer- problems and indicates how todevelop a theory which parallels
ence limiting rules) and that minimizes the amount of spec- that of Section I11 for these problems. We also discuss other
trum tied up by the assignment. optimization problems some of which appear to be related to
It is sometimes convenient to differentiate between two frequency assignment problems. In Section VI, guided by our
types of frequency assignmentproblems. If the assignments efforts in Sections 111, IV, and V, we formulate and investigate
are c o n f i e d to discrete, butnot necessarily evenly spaced generalized graph coloring problems and, once again, indicate
frequencies and we wish to emphasize thisfactthenthe how to develop a theory for these problems that parallels that
problem is called a channelassignment problem. We some- of Section 111. In SectionVII, we showthat each of the
times conserve space and write assignment instead of channel assignment problems of Sections 111, IV, and V is equivalent
(or frequency) assignment. It is important to differentiate be- to a generalized graph coloring problem. Using these equiva-
tween two typesof interference limiting constraints. One type lences, we areable to classify many real world assignment
of constraint specifies that if the distance between two trans- problemsaccording to theircomputationalcomplexity. In
mitters is less than a prescribed minimum number of miles Section VIII, we conclude with a summary and a discussion of
then certain combinations of assignments to this pair of trans- real world applications of our findings. In addition, we suggest
mittersaretabooorforbidden. Such constraintsemploy topics for further study.
HALE: FREQUENCY ASSIGNMENT 1499

11. DEFINITIONS AND NOTATION directional and all have the same power and operating band-
This paper contains thefollowing notations and terminology. width. Spectrum managers sometimes make these assumptions
X is a subset of Y , X C Y ;X is a proper subset of Y,X C Y ;A when taking a nationwide or regional approach to an assign-
is a function from X into Y (or A is an assignment of members ment problem (e.g., UHF-TV as in [82]). We investigate the
of X to members of Y ) . A :X+ Y ;the cardinal number of the traditional minimum span approach to channel assignment and
set X, 1x1;the empty set { } ; the integers Z ; the rationals Q; showthatfor some situations anew approach called the
the positive integers, rationals and reals, respectively Z’, Q’, minimum-order approach may be moredesirable. We show
and R’; the nonnegative integers, rationals and reals, respec- that the distinction between the minimum span approach and
tively Z:, Q:, and R: ;the absolutevalue of the number a , la I ; the minimum-order approach is lost on the cochannel assign-
the largest number in X, afinite nonempty subset of Z : , ment problem. In addition, we develop a theory which relates
max X;the smallest number in X,a nonempty subset of Z , , the two approaches and their common subproblem. Finally,
min X;the greatest lower bound of X,a nonempty subset of for the reader who does not wish t o work through the proofs
Q:, inf X;the Euclidean distance between u and u , two points of theorems, there is a summary at the end of this section in
in the plane D ( u , u ) . If A : X + Y and x belongs to X , then which we present an informal discussion of the theory.
A ( x ) is the element of Y that A assigns to x and A ( X ) equals
A . The Frequency-Distance Constrained Cochannel
{ A ( x ) l x belongs to X } . If a and b belong to Q then, (a, b)Q
Assignment Problem
equals {c 1 c belongs t o Q and a < c < b } and [ a , bQ] equals
<
{cl c belongs to Q and a c < b } . The paper [ 131 discusses the following searchproblem
If V is a finite set and E is a specified set of two element called the F*Dconstrainedcochannelassignmentproblem
subsets of V , then G = ( V ,E ) is a graph with vertex set V and (F*D-CCAP). Given V a finite subset of the plane and d a
edgeset E . To simplify notation,thetwo elementsubset positive rational number, the problem is to find an assignment
{ u , u } belonging to E is denoted by uu. If G = ( V , E ) and uu A : V + 2’ which satisfies the conditions
belongs t o E then u and u are adjacentvertices in G . The max A ( V ) is as small as possible and
(1)
graph G = ( V , E ) is complete if uu belongs to E whenever
u # u. The graph G’ = ( V ’ ,E ’ ) is a subgraph of the graph if u and u are elements of V , u # u and D ( u , u ) < d
G = ( V ,E ) if V’ 5. V and E ’ C E. If G = ( V , E ) , V‘ 5. V , and then A ( u ) # A(u). (2)
E’ = {uuluv belongs to E , u and u belong to V ’ } , then the
The set V may be thought of as the locations of radio trans-
graph ( V ‘ ,E’) is denoted ( V‘) and is called the subgraph of G
mitters and A : V + Z + as an assignment of channels to these
induced by V‘. If H is a complete subgraph of G and His not
transmitters. Thus the assignment A assigns the channelA(u)
properly contained in a complete subgraph of G, then H is a tothetransmitterlocatedat u . Condition (2) requires that
clique of G . The clique number of G is the number of vertices
transmitters assigned tothe samechannel (i.e., cochannel
in the largest clique of G and is denotedby W ( G ) . The transmitters) be separated byadistancegreater than d . For
chromatic number of G is denoted by X ( G ) and is the mini-
this reason, condition (2) is called a cochanneZ constraint. An
mum number of colors necessary to color the vertices of G
assignment A : V + Z + which satisfies (2) is called a feasible
such that no two adjacent vertices receive the same color. A assignment for V and d . The condition (1) is motivated by
graph G is perfect if X ( H ) = W(H) for every induced subgraph
our desire t o conserve spectrum; and if A : V + Z + is a feasible
H of G.
assignment for V and d which satisfies (1) then A is called an
A graph G = ( V ,E ) is called an intersection graph for F , a
optimalassignment f o r V andd and max A ( V ) is denoted
family of sets, if there existsaone-to-one correspondence,
m( V , d ) . Thus { 1, 2, * , m( V , d ) } is the smallest set of chan-
f:V + F , suchthat uu is an element of E if and only if
nels which will accommodate an assignment of channels to the
f ( u ) and f ( u ) have nonemptyintersection. Conversely, F is
called an intersection model for G if G is an intersection graph transmitters in V , whichdoes not violate thecochannel
for F . If F is a finite collection of intervals on the real line constraint.
then an intersection graph for F is called an interval graph. If Throughoutthe rest of thispaper we will use a standard
formatfor specifyingsearchproblems.A restatement of
F is a finite collection of arcs on a circle then an intersection
F*D-CCAP illustrates this format.
graph for F is called acircular-arc graph. If, in addition, no
arc in F contains another arc, G is called a proper circular arc F*D-CCAP (problem name)
graph. INSTANCE: V afinitesubset of the planeand d 0 a >
rational number.
111. FREQUENCY-DISTANCE
CONSTRAINEDCHANNEL FIND: A : V + Z’ a feasible assignment for V and d such
ASSIGNMENT PROBLEMS that max A ( V)is as small as possible.
Complex frequency assignment problems are most easily The standard format consists of three parts: the first part is
discussed in terms of formal models. In this paper, all assign- the problem name, the second part specifies a generic instance
ment problems are modeled as optimization problems. All but of the problem, and the third part describes, in terms of the
three of these are combinatorial optimization problems called generic instance, the object(,) of the search. For each of the
search problems [ 23 1. For our purposes, it is not necessary search problems of this paper, we establish that the search will
to give a rigorous definition of “search problem.” The concept not be fruitless; i.e., for each generic instance there exists at
will be amply illustrated by many examples. In this section, least one object of the search. Therefore, for our purposes, an
we investigate cochannel, adjacent channel, and more complex algorithm (or computer program) is called a solution of the
frequency-distance constrained channel assignment problems. search problem S if it accepts as input any generic instance of
We assume that everything is uniform. That is, the terrain is the problem S and returns as output an object of the search.
uniform; the receivers are uniform; the transmitters are omni- A search problem is undecidable if it is impossible t o specify
 1500 PROCEEDINGS OF THE IEEE, VOL. 68, NO. 12, DECEMBER 1980

any algorithm which is a solution. An algorithm runs in poly-

nomial time if it always terminates within a number of steps
I I I I I
1
which is bounded above by some polynomialin the size of the
input. A solution of asearch problem is called an efficient
solution if it runsinpolynomialtime.Forexample, given

I
V = (ul,u2, - - ,u,} and d an instance of F*D-CCAP, let
F( V , d ) consist of all A : V + { 1,2, ,n } which are feasible
assignments for V and d . F( V , d ) is notempty since
A : V + ( 1 , 2 ; - . , n } defined A ( u i ) = i for i = l ; - * , n is 2 (31

feasible. An exhaustive search of the finite set F( V , d ) will

yield anoptimal assignment for V and d . This exhaustive 2
search can beformalized as an algorithmwhich solves F*D-
CCAP. Therefore F*D-CCAP is decidable. Forfuture refer-
3
ence we formalize these conclusions.
Theorem I: If Vis a finite subset of the plane and d > 0 is a
-
rational number, then thereexists A : V + ( 1 , * * ,m( V , d ) } an
optimal assignment for Vand d . I I I 1 I
Theorem 2: F*DCCAP is decidable. - 1 0 1 2 3 4 5 6
Exhaustive search algorithms are inefficient and, in practice, Fig. 1. Graphical depiction of the set of transmitter locations, the for-
bidden combinations of channel assignments, the minimum span as-
can only beapplied to “small” problems. The likelihood of signment A , and the minimum-order assignment B of Example One.
our finding an efficient solution for FIDCCAP will be dis-
cussed in Sections VI1 and VIII. The reader who is interested
in learningmore about searchproblems andtheircomputa- C . Example One: A Minimum Span Assignment
tional complexity is referred to [ 231. That Wastes Spectrum
Let V = ((0, O), ( 0 , 1 ) , ( 3 , 1 ) , (3, 2 ) , ( 3 3 4 1 , ( 4 , 3 ) , (5,5),
B . The Frequency-Distance Constrained Adjacent ( 6 , 6 ) } and D = { d ( O ) , d ( l ) }where d(0)=1.415 and d ( l ) = l .
Channel Assignment Problem (F*D-ACAP)
One can show by exhaustive search that A : V + ( 1 , 2 , 3 ) de-
The paper [ 131 discusses the following assignment problem. fined by A ( 0 , l = ) A ( 3 , 2 ) = A ( 3 , 4 ) = A ( 5 , 5 )= l , A ( 0 , O ) =
Let V be a finite subset of the plane and let D = (d(O), d(l)} A ( 3 , 1) = 3 , and A ( 4 , 3 ) = A ( 6 , 6 ) = 2 is a minimum span as-
where d ( 0 ) > d ( 1 ) > 0 are rational numbers. If A : V + Z + signment for V and D . However, B : V + { 1 , 2 , 3 } defined by
satisfies the condition, if u and u are elements of Y, B ( 4 , 3 )= B ( 6 , 6) = 3 and B(u) = A ( u ) otherwise is feasible for
Vand D . In addition, B uses only two channels whereas A uses
u f u and D(u, u ) d ( i )< three. Thus minimum span assignments may waste spectrum.
then Notice that B is also a minimum span assignment for Vand D .
One can show that no feasible assignment for V and D uses
I A ( u ) - A(u) I # i, for i = 0,1, ( 3 ) fewer thantwo channels. Therefore B is called aminimum
then A is called a feasible assignment for Vand D . When i = 0, order feasible assignment for V and D (where the order of an
( 3 ) becomes a cochannel constraint and requires that cochan- assignment is thenumber of channelsactually used by the
ne1 transmitters be separated by a distance greater than d ( 0 ) . assignment). Fig. 1 depicts this example graphically. Inthis
When i = 1, equation ( 3 ) becomes an adjacent channel con- figure, transmitters separatedbyadistance equal to or less
straintand requires thattransmitters assigned to adjacent than the adjacent channel distance requirement ( d ( 1 ) = 1) are
channelsbe separated byadistance larger than d ( 1 ) . An connected by a wavy line and cannot be assigned the same or
adjacent channel constraint is required, inpractice, when a adjacent channels.The transmitters separatedbyadistance
receiver tuned to a transmitter in V cannot tolerate the inter- larger thanthe adjacentchanneldistance requirementbut
ference generated by adjacent channel transmitters which are equal to or less thanthecochannel distance requirement
“close” (in distance) to the receiver. ( d ( 0 ) = 1.41 5) are joined by a smooth line and cannot be as-
If A is a feasible assignment for V and D , then we say that signed the same channel (but may be assigned adjacent chan-
L = max A ( V) accommodates V and D and the smallest such L , nels). The numerals adjacent to the transmitter locations (but
denoted m ( V , D ) , is called theminimum span o f a feasible not inparentheses) constitute theminimum span assignment A .
assignment for V and D . If A : V + ( 1 , --
, m( V ,D ) } is feas- The numerals in parentheses constitutethe minimum-order
ible for V and D , then A is called a minimum span assignment assignment B . Can it be that all of the minimum span assign-
for Vand D. ments, for a particular problem, waste spectrum?

F*D-ACAP D. Example Two: All Minimum Span Assignments

INSTANCE: V a finite subset of the plane and D = Waste Spectrum
{d(O), d( 1 ) ) where d(0) and d( 1) are positive rational numbers. Let V = ( ( 2 , - 2 ) , ( 2 , 01, ( 2 , I), ( 2 , 31, (3, 21, (4, 0)) and
FIND:A : V + (1, * , m( V ,D ) } a minimum span assign- D = { d ( O ) , d ( l ) } where d ( 0 ) = 3 and d(1) = 2. One can show
ment for Vand D . by exhaustive search that six is the minimum span of a feasible
assignment for V and D and that each of the minimum span
Traditionally (see [ 9 ] ,[ 131, [ 171, and [ 181), minimum span assignments for V and D has order five or six. However,
assignments have been regarded as mathematically optimal A : V + {1,2, -
7 ) defined by A ( 2 , - 2 ) = 3 , A ( 2 , O ) = 7 ,
a ,

from the point of view of minimizing spectrum waste. Can a A ( 2 , l ) = 5, A ( 2 , 3 ) = 1, A ( 3 , 2 ) = 3 and A ( 4 , O ) = 1 is a feasible
minimum span assignment waste spectrum? assignment for Vand D that uses only four channels. Therefore,
HALE: FREQUENCY

3t
2C

-‘t
-21
.
I
Fik 2. Graphical depiction of the set of transmitter locations, the for-
biddencombinations of channelassignments,aminimumspan
signment and the minimum order assignment A of Example Two.

incertain situations, A is more desirable than any minimum

as-
The pair (T(O),d ( 0 ) ) is called UHF-TV’s cochannel constraint,
since for i = 0,(5) requires that cochannel stationsbe separated
by more than 155 mi. Similarly, the pair (T( l ) , d( 1)) is called
UHF-TV’s 15th adjacent channel constraintsince for i = 1, (5)
requires thattransmitters assigned to channelsseparated by
exactly 15 channels be separated by more than 75 mi; the pair
(T(2), d ( 2 ) ) is called UHF-TV’s 7th and 14th adjacent channel
constraint since for i = 2 (5) requires that transmitters assigned
to channels separated by exactly 7 or 14 channels be separated
by more than 60mi, etc. The pairs ( T ( i ) , d ( i )for
) i = 1,2,3,4
are F*D constraints related to the UHF-TV receiver rejection
characteristics. The paper [ 821 discusses this relationship and
the possibility that improvements in receiver rejection charac-
teristics may allow fortherelaxation
constraints.
of some of these

The UHF-TV assignment problem is more involved than

F*D-CCAP or F*D-ACAP andonce again aminimumspan
assignment may fail to beaminimum-orderassignment.

u2 = (75,loo), u 3 = (100,80), u4 =(120,80), and us =,

(100,150). One can show by exhaustivesearch that A : +
span assignment for V and D (since each of the minimum span {l,2,3,4,5,6,7}definedbyA(u1)=4,A(u2)=3,A(u3)=1,
assignments uses more channels). Fig. 2 depicts this example A ( u 4 ) = 7, and A ( u , ) = 2 is a minimum span assignment for V
To
illustrate, let V = {ul ,u 2 , u 3 ,u4, u s } where u1 = (20, lo),
1501

graphically. subjecttotheUHFtaboos. S i m i l a r l y B : V + { 1 , 2 , 3 , 4 , 5 , 6 , 7 }
The distinction between minimizing the span of an assign- defined by B ( u l ) = 2 and B(ui) = A ( q ) for i = 2 , 3 , 4 , 5 is a
ment versus minimizing the order is lost on F*D-CCAP since minimum-order assignment for V which is more desirable than
every minimum span assignment for an instance of F*D-CCAP A . Fig. 3 depicts thisexamplegraphically. In this figure,
is also a minimum-order assignment (see Theorems 15 and 26 transmitters separated by any distance d that is equal to or less
below). However, the majority of real world assignment than the cochannel distance requirement ( d ( 0 )= 155) are con-
problems are more complex than F*D-CCAP. And for these nected by a line and this line is labeled with T ( i )if d(i + 1) <
more complex problems it is easy to find exampleslike the d < d ( i ) . Thus, if two transmitters ui and ui are connected by
ones above. That is, minimum span assignments which fail to a line that is labeled with T ( i ) then any feasible assignment A
have minimum order abound in the real world. It is important must have the property I A(ui) - A(ui) I is not an element of
that we investigate this potentially useful phenomenon. Before T ( i ) (e.g., I A ( u 2 )- A ( u s ) I cannot belong to- {0,7,€4, 15},
defining the searchproblemswhich capturethe essence of IA(u,)- A(u,)l cannot belong to (0,1,7, 14, 15},etc.). The
minimumspan and minimum order, we present another ex- numerals adjacent to the transmitter locations constitute the
ample to furthermotivate the following definitions and theory. minimumspan assignment A . The numeralsinparentheses
constitute the minimum-order assignment B .
E . ExampleThree:UHF-TV
F*D constraints, other than cochannel and adjacent channel F. A General Minimum Span Channel Assignment
are often imposed in practice. For example, if V is aset of Problem (F*D-CAP)
locations of UHF-TV transmitters in the Eastern U.S., then If d ( 0 ) > d( 1) > * * * > d ( m ) > 0 are rational numbers and
A : V + Z + is a feasible assignment of channels for I/‘ if and (0) = T ( 0 ) C T( 1) C * * * C T ( m ) are finite subsets of Z i then
only if the following condition is satisfied. R = { ( T ( i ) , d ( i ) ) l i= 0,.* * , m } is called aset of F*D-
If u and u are elements of V , u # u , and D ( u , u ) < M ( i ) then constraints. If k 2 0 and k is an element of T ( j )but k is not an
IA(u)-A(v)I#i, fori=0,1,2,3,4,5,7,%,14,and15.
element of T( j - 1). then the pair (T(j ) , d( j ) ) is called R ’s kth-
channel constraint, and d ( j ) is called R’s kth-channel distance
(4) constraint. R’s Oth-channel constraint is also called R’s co-
channel constraint; R’s lst-channelconstraint is also called
Where, M ( O ) = 155, M(1)=55, M(2)=M(3)=M(4)=M(5)=
R’s adjacent channel constraint; and for k 2 2, R’s kth channel
M(8) = 20, M(7) = M(14) = 60 and M(15) = 75 are mileage constraint
is also called R’s kth adjacent channel constraint.
separations required of transmitters assigned to channels sepa- Let V be a finite subset of the plane and let R =
rated by 0, l , 2 , 3 , 4 ,5, 8,7,14, and 15 channels, respectively. {(T(i), d(i))li = 0, 1, * . . , m } be a set of F*D constraints. If
There is no mileage separationrequirementfortransmitters A : V + Z + satisfies: I A ( u ) - A ( u ) I is not an element of
separatedby 6,9, 10, 1 1, 12, 13, 16, 17, * - channels. Let
R = { ( T ( i ) , d ( i ) ) I i = 0 , 1 , 2 , 3 , 4 } where T(O)= {0}, T(1)= T ( i ) whenever u # u and D ( u , u ) < d ( i ) , for i = 0,1, * * * , m ,
(0,15), T(2)= {0,7, 14, 15}, T(3)= (0,1 , 7 , 1 4 , 151, T(4)=
{0,1,2,3,4,5,7,8,14,15},d(O)=155,d(l)=75,d(2)=60, (6)
d ( 3 ) = 5 5 and d ( 4 ) = 20. The following condition is acon- then A is called a feasible assignmentf o r V a n dR . Thus, if the
venient way to express (4). If u and u are elements of V , distance between two transmitters u and u is less than or equal
u # u, and D ( u , u ) < d(i), then to d ( i ) , then certain combinations of assignments to this pair
oftransmittersaretaboo. In particular,any assignment in
IA(u) - A(u)l is not an element of T ( i ) , for i = 0,1 , 2 , 3 , 4 . which I A ( u ) - A(u)I is an element of T ( i ) is forbidden by
(5) condition (6).
 1502 IEEE,OF THE
PROCEEDINGS VOL. 68, NO. 12, DECEMBER 1980

Let F ( V , R ) denote the set of all feasible assignments for V max A(V) = m0(V , R , a),
then A is called a minimum-order
and R. Let Q belong to Z+ and let F ( V ,R , Q)denote {A J A is assignment for V and R in L. We are now ready to formulate
an element of F ( V , R ) and max A( V) < 1). If I VI = n , then let a minimum-order search problem called the F*D-constrained
M = 1 + m a x { m a x T ( i ) l i = O ; * - , m ) and let M ( V , R ) = l + minimum-orderchannel
assignment
problem
with
limited
( n - 1)M. bandwidth.
Theorem 3: I f ?! 2 M ( V , R), then F( V , R , 2 ) is not empty.
Proof: Let u l , u 2 , , u , be a list of V and define
F*D-CAPOL
A:V+{1,2;**,!d)byA(ui)=l+(i- l)Mfori=l,2;*-,n INSTANCE: V a finitesubset of theplane, R a set of
It is easy to see that A is feasible for V and R and that F*D-constraints and Q 2 m( V , R).
max A( V) = M( V ,R). Q.E.D. FIND: A : V + L = { 1 , 2 , * , a}
aminimum-order assign-
ment for Vand R in L .
Since F( V ,R, Q)C F ( V , R ) for each Q, we have the following
result as a corollary t o Theorem 3. By Theorem 5, F( V , R , 2 ) is not empty when Q 2 m( V , R).
Theorem 4: F ( V , R ) is not empty. Therefore, by exhaustive search there is a feasible assignment
If A is an element of F( V , R ) then we say that Q = max A( V ) A : V + L which uses exactly o( V , R , Q)channels and no assign-
accommodates V and R. The smallest such Q is denoted ment A' which is an element of F ( V , R , Q)uses fewer than
m ( V , R ) and is called the minimum span of a feasible assign- o( V , R , !?) channels. Again by exhaustive search (this time on
ment for Vand R. Thus m ( V , R ) = min {max A(V)IA is an the nonempty fiiite set {A I A is an element of F( V ,R , Q)and
element of F ( V , R)} and the following results areimmediate. o(A) = o( V , R , Q)}) there is a feasible assignmentA : V +
Theorem 5: F( V , R , 2 ) is notempty if andonly if (1, 2, * * , mo ( V , R , Q)} which uses exactly o( V , R , Q)chan-
Q 2 m( V , R). nels and mo ( V , R , 2 ) < Q is the smallest number of channels
Theorem 6: m( V , R ) <M( V,R). that will accommodate such anassignment. We formalize these
If A is an element of F ( V , R ) and maxA( V) = m( V ,R ) then results as theorems.
A is called a minimum span assignment for V and R . We now Theorem 9: If Q 2 m( V , R), then there exists A : V + L =
formulate a general minimum span search problem called the a}
(1, 2, * , a minimum-order assignment for Vand R in L .
F*D constrained channel assignment problem. Theorem 10: F*DCAPOL is decidable.
An algorithm which solves F*D-CAPOL also solves any sub-
F*D-CAP
problem of F*D-CAPOL including F*D-CCAPOL, F*D-
INSTANCE: V a finite subset of the plane, and R a set of
ACAPOL, and F*D-UHFOL (where these subproblems are ob-
F*D constraints.
tained by restricting the form of R exactly as was done in
FIND: A : V + { l ; - * , m ( V , R ) } aminimumspan assign-
Example Four). In Example One above, A is a minimum span
ment for V and R.
assignment for Vand R but is not a minimum-order assignment
Recall that an algorithm solves F*DCAP if, given V and R as for V and R in L = (1, * * , 6). Therefore, F*D-ACAP is not
input, it returns aminimumspan assignment for V and R. equivalent to F*D-ACAPOL. We shall see (Theorem 15 below),
Since F ( V , R , Q)is f i i t e and nonempty (where Q = M( V ,R)) however, that F*DCCAPOL is equivalent to F*DCCAP.
an exhaustive search will yield a minimum span assignment for -
If R = { ( T ( i ) ,d ( i ) )I i = 0,* * , m } is a set of F*D constraints,
Vand R. then let R, denote {(T(O), d(O))},R's cochannel constraint.
Theorem 7: If V is a fiiite subset of the plane and R is a set Let m,( V , R ) denote max A ( V ) where A is an optimal assign-
-
of F*D constraints, then thereexistsA : V + (1, * * , m( V , R)} ment for V and R,. Notice that V and R, is an instance of
F*D-CCAP and that 11, * * * , mc( V , R)} is the smallest set of
a minimum span assignment for V and R .
Theorem 8: F*DCAP is decidable. channels which w li accommodate a feasible assignment for V ,
Example Four: An algorithm which solves F*D-CAP also when only R's cochannel constraint must be satisfied. We will
solves anysubproblem of F*D-CAP. Each of the minimum show that for every Q 2 m( V , R), mc( V , R ) is a lower bound
span search problems discussed earlier in the section are sub- on the minimum order of a feasible assignment for V and R
problems of F*DCAP and may be obtained from F*D-CAP by in L.
restricting the form of R . For example, F*D-CCAP is obtained Theorem 11: If A is an element of F( V , R , a), then o(A) <
when R is restricted to have the form {( {0}, d(O))};F*D-ACAP max A ( V ) .
is obtained when R is restricted to have the form {( {0}, d(O)), -
Proof: A( V) C { 1, * * ,max A( V ) } therefore o(A) <
((0, l}, d ( l ) ) } ;and F*DUHF is obtained when R = {({0}, max A ( V ) . Q.E.D.
155),({0,15},75),({0,7, 14, 15},60), ((0, 1 , 7 , 1 4 , 15},55), Theorem 12: If A is an element of F( V, R, Q)and maxA( V )=
((0, 1, 2,3,4, 5,7,8, 14,15},20)). m,( V , R), then A is an element of F( V , R,) and o(A) =
m,( V , R).
G. A General Minimum-Order Assignment Problem with Proof: If A is an element of F ( V ,R , Q), and u and u are
Limited Bandw'dth (F*D-CAPOL) elements of V , then I A(u) - A(u)l is not an element of T ( i )
If A is an element of F ( V , R), then I A ( V )I is called the order whenever u # u and D(u, u ) < d ( i ) for each i = 0,1, ,m .
of A and is denoted o(A). Thus o(A) is the number of chan- Therefore, I A(u) - A(u)( # 0 whenever u # u and D(u, u ) <
nelsactuallyusedbyA. IfQ>m(V,R)andL= {1,2;*.,Q}, d ( 0 ) since 0 is an element of T ( i ) for each i = 0,* * , m . In
then min {o(A) I A is an element of F ( V , R , Q)}is called the other words, A is an element of F(V, R,J.By Theorem 11,
minimum order of afeasibleassignment for V and R in L o(A) < max A( V )= mc( V , R). Assume that o(A) # m,( V , R )
and is denoted o( V , R , 2). Let mo( V , R , Q) denote and therefore that o(A) < m,( V , R). It follows that A(V) is a
-
min {max A( V ) l A is an element of F( V , R , Q)and o(A) = proper subset of (1, * , m,( V , R)}. Therefore, let M be the
-
o ( V , R , g ) } . I f A b e l o n g s t o F ( V , R , Q ) , o ( A ) = o ( V , R , Q ) , a n d largest element of (1, * , mc( V , R)} which is not in A( V )
 HALE: FREQUENCYASSIGNMENT 1503

is easy t o show that A is an element of Fo(V , R ) and that

anddefineA:V+{l,-*~,M}byA’(u)=MifA(u)=m,(V,R)
and A ’ ( u =) A ( u ) otherwise. Now A’ is an element of maxA(V)=Mo(V,R)<Q. Q.E.D.
F( V ,R,) since if u and u are elements of V and u # u : Theorem 19: Fo( V , R ) is not empty.
Case 1: If A ( u ) # m , ( V , R ) and A ( u ) = mc( V ,R ) , then
A’(u) = A ( u ) is an element of A( V),A’(u) = M is not an ele- H. A General Minimum-Order Assignment Problem
ment of A ( V ) and therefore A ’ ( u ) # A ’ ( u ) : With Unlimited Bandwidth (F*D-CAPO)
Case 2: If A ( u ) = A ( u ) = m,( V , R ) , then D ( u , u ) > d ( 0 ) ; The integer min {max A ( V ) (A is an element of Fo( V , R ) } is
Case 3: If A ( u ) # m , ( V , R ) and A ( u ) # m c ( V , R ) , then called the minimum span o f a minimum-order feasible assign-
~ o since A is an element of
I ~ ’ ( u- )A ’ ( U ) =~ I ~ ( u- )A ( u ) # ment for V and R and is denoted mo ( V , R ) . If A is an element
F ( V ,R c ) . of F o ( V , R ) and maxA(V)= m o ( V , R ) , then A is called a
Therefore, we have A’ is an element of F( V , R,) and by minimum-order assignment for V and R . The following results
definition of A ’ , max A’(u) = M < m,( V ,R ) . This is impos- are immediate.
sible since by definition m,( V ,R ) = min {max A( V)I A is an Theorem20: Fo( V ,R , Q ) is notempty if and only if
element of F( V , R,)}. Therefore o ( A ) = mc( V ,R ) . Q.E.D. Q 2 mo( V ,R ) .
Theorem13: If A is an element of F( V , R , a) and Theorem 21: mo(V, R ) <Mo(V,R ) .
max A ( V ) = m,( V ,R ) , then A ( V )= {1,2, - , m,( V ,R ) } . We arenowready to formulate asecond minimum-order
Proof: A(V)C{1,2;**,mc(V,R)} byTheorem 11,and search problem called the F*D-constrained minimum-order as-
inclusion cannot be proper since otherwise o ( A ) < mc( V ,R ) signment problem (with unlimited bandwidth).
which is impossibleby Theorem
12. Q.E.D.
Theorem14: If A is an element of F( V , R , Q) and F*D-CAPO
max A( V ) = m,( V , R ) , then o ( A ) = m,( V , R ) = o( V , R , Q)= INSTANCE: V a fmite subset of the plane, and R a set of
mo(V,R,Q). F*Dconstraints.
Proof: By Theorem 12,o ( A ) = mc( V ,R ) and by definition FIND: A : V + (1, 2, -
, mo( V ,R ) } a minimum-order as-
o( V,R , Q)< o ( A ) = m,( V,R ) . Suppose that, o( V ; R , Q)< o ( A ) signment for V and R .
and let A’ be an element of F( V ,R , Q)such that o(A‘)=
o( V , R , 9). Let Ci, i = 1, * * , o(A‘) be an indexing of A‘( V) Theorem 22: If V is a finite subset of the plane, and R is a
and define A ” : V + 11, 2, * * * ,o(A’)}by A“(u) = i if A’(u) = Ci. set of F*D rules, then there existsaminimum-order assign-
Now A“ is an element of F( V ,R,) and max A”( V)= o(A’)< ment for V and R .
m,( V , R ) which is impossible. Therefore o ( A ) = o(A’)= Proof: By Theorem 18, if Q = Mo(V,R ) , then Fo( V ,R , Q)
o( V ,R , 2). We now have A is an element of F( V ,R , Q)and is f i i t e and not empty. Thus an exhaustive search will yield a
o ( A ) = o( V ,R , Q), therefore, by definition of mo( V , R , Q), minimum-order assignment for V and R . Q.E.D.
maxA(V)>mo(V,R,Q). But m , ( V , R ) = m a x A ( V ) > Theorem 23: F*D-CAPO is decidable.
mo( V , R , Q)is impossible since if A * is a minimum-order as- Any algorithm which solves F*DCAPO also solves F*D-
signment for V and R in L , then A* is an element of F( V ,R E ) CCAPO, F*D-ACAPO, and F*D-UHF0 (where these subprob-
(byTheorem12)and maxA*(V)=mo(V,R,Q)>m,(V,R) lems of F*DCAPO are obtained by restricting the form of R
definition
by of m,( V , R ) . Q.E.D. exactly as was done in Example Four).
The following result is an immediate corollary. Theorem 24: If A is an element of F( V,R , 2) and max A ( V ) =
Theorem 15: F*D-CCAP is equivalent to F*D-CCAPOL. mc( V ,R ) , then o ( A ) = m,( V ,R ) = o( V ,R , Q)= m( V ,R ) =
Theorem 16: If A is an element of F( V ,R ) , then mc( V ,R ) < mo(V,R,Q)=mo(V,R).
44). Proof: See 14. Theorem Q.E.D.
Proof: Suppose o ( A ) < m,( V,R ) and let Ci, i = 1, * * * , o ( A ) , We have the following two results as corollaries.
be an indexing of A ( V ) . Define A ’ : V + {1,2, * * * , o ( A ) } by Theorem 25: If m,( V ,R ) = m( V ,R ) and Q 2 m( V , R ) , then
A’(u) = i if A(u) = Ci. Clearly A is an element of F( V ,R,) and m,(V,R)=o(V,R,Q)=m(V,R)=mo(V,~,Q)=mo(V,R).
max A‘( V )= o ( A )< m,( V ,R ) which is impossible. Q.E.D. Theorem 26: F*D-CCAPO is equivalent to F*D-CCAP.
As promised, we have the following result as acorollary. F*D-ACAPO is not equivalent to F*D-ACAP byExample
Theorem 17: If Q > m( V ,R ) , then mc( V , R ) < o( V ,R , a). One.
By Example One, mc( V ,R ) is the best possible lower bound. Theorem 2 7: If Q > m ( V , R ) , then m , ( V , R ) < m ( V , R ) <
Taking into account Theorem 15, we say that A an element of mo(V, R , Q).
F( V ,R ) is a minimum-order feasible assignmentf o r V and R if Proof: By the definitions of m , ( V , R ) , m ( V , R ) , m o ( V ,
o ( A ) = m,(V, R ) . Let Fo(V , R ) denote the set of all such as- R , 2) and the fact thatF( V,R , Q)C F( V , R ) C F ( V , R,).
signments. Let ?! be an element of Z + and let Fo( V ,R , Q)de- Q.E.D.
note { A I A is an element of Fo(V , R ) and max A ( V )< Q}. Let Theorem28: I f Q > m ( V , R ) , t h e n m , ( V , R ) < o ( V , R , Q ) <
-
M = 1 + max {max i“(i)l i = 0,. , m } and let Mo(V,R)= m ( V , R).
1 + ( m , ( V , R ) - 1)M. Proof: By definition o ( V , R , 2) = min { o ( A ) I A is an ele-
Theorem18: If Q 2 M o ( V , R ) , then F o ( V , R , Q) is not ment of F ( V , R , Q)}. Therefore, m , ( V , R ) < o ( V , R , Q)by
empty. Theorem 1 6 , a n d o ( V , R , Q ) < m ( V , R ) b y T h e o r e m 11.
Proof: By Theorem1,there exists A’ an element of Q.E.D.
-
F( V ,R,) such that A ‘ : V + {1,2, * , m,( V ,R ) } . For each Theorem29: I f Q > m ( V , R ) , t h e n r n , ( V , R ) < o ( V , R , Q ) <
i = 1, * * , m,( V , R ) denote {ul A‘(u) = i } by Vi. Define m(V,R)<mo(V,~,Q)<mo(V,R).
A : V + { 1 , 2 ; * * , Q ) b y A ( u ) = l + ( i - 1)Mforeachuanele- Proof: It remains to show that m o ( V , R , Q)< m o ( V , R ) .
ment of (where M = 1 + max {max T ( i )I i = 0 , - , m } ) . It Suppose to the contrary that m o ( V ,R , Q)> m o ( V , R ) . Let A
 1504 PROCEEDINGS OF THE LEEE, VOL. 68, NO. 12, DECEMBER 1980

be an element of F ( V , R , Q) such that o ( A ) = o ( V ,R , Q) and assignmentproblemsintersectin thecochannelassignment

m a x A ( V ) = m o ( V , R , 2). Now m o ( V , R , Q ) > m o ( V , R ) im- problem (Theorems 15 and 26).
plies that if A’ is an element of F ( V , R ) such that o ( A ’ ) = More concretely, if V is a set‘of locations of UHF-TV sta-
m,(V, R ) , then maxA’(V)<mo(V, R,Q)=maxA(V). Thus tions in theEastern US., and R is the coIledion of UHF
it follows that A’( V ) C (1, * * * I max A ( V ) }C (1, * * ,Q}and taboos (see Example Three) for this region, then a minimum
A’ is an element of F ( V , R , Q). By definition of o ( V ,R , !?),we span assignment for V and R requires exactly m (V,R ) cham
have, o ( V , R , Q ) < o ( A ’ ) = m , ( V , R ) andbyTheorem16, nels. If the number of contiguous channels available for as-
o ( V , R , Q)=m,(V, R ) . Now, by definition, m o ( V , R , Q ) < signment is smaller than m (Y, R) then there is no assignment
max A ’ ( V ) which contradictstheabove result that max of channels to V that satisfies each of the UHF taboos. If R ,
A ‘ ( V )< mo(V , R , Q). Q.E.D. denotes R’s cochannel constraint(i.e., R, = {({0}, 155))) then
Example Two shows that eachof the inequalities in Theorem m,(V, R ) = m( V , R , ) the span (and the order) of an optimal
29 may be strict. That is, for Q = 6, m,(V, R ) < o ( V , R ,9 ) assignment for V and R , is equal to orless than both the span
and m o ( V , R , Q ) < m o ( V , R ) ; andfor Q = 7 , o ( V , R , Q)< and the order of any feasible assignment for V and R. If there
m(V,R)andm(V,R)<mo(V,R,L). are mo(V , R ) contiguous channels available for assignment,
Theorem 30: If 2‘ 2 Q 2 m ( V , R ) then o ( V , R , 2’) < o ( V , then there is afeasibleassignment for Y and R which uses
R,Q)andmo(V,R,Q)<mo(V,R,Q’). exactly m,( V , R) of the mo(Y, R ) contiguous channels. The
Proof: o ( V , R , Q ‘ ) < o ( V , R , Q ) b y d e f i n i t i o n o f o ( V , R , Q )span of such an assignment is exactly mo(Y,R). If there are C
since F ( V , R , Q)C F ( V , R ,Q’). m o ( V , R , Q ) > m o ( V , R ,Q’) contiguous channels available for assignment and m(Y, R) <
leads to a contradiction by an argument identical to the one C < mo(V , R ) , then each feasible assignment for Y and R in
he in Proof of Theorem 29. Q.E.D. C has order greaterthan m, (V, R).
Theorem-31: I f , l ? > m o ( V , R ) , t h e n m , ( V , R ) = o ( V , R , Q )
andmo(V,R,Q)=mo(V,R). Iv. FREQUENCY CONSTRAINED CHANNEL
Proof: By Theorem 29, m, ( V , R ) 4 o ( V , R, Q). Suppose ASSIGNMENT PROBLEMS
mc(V,R)<o(V,R,Q),andletA beanelementofF(V,R,Q) The search problems discussed in Section III model existing
suchthat o ( A ) = o ( V , R , 2) and maxA(V)=Mo(V, R, Q). and potential real world problems (e.&, the present UHF-TV
Now,o(V,R,Q)>m,(V,R)impliesthatifA’isanelementof problem and potential future variations upon this problem).
F(V,R)suchthato(A‘)=m,(V,R),thenm,(V,R)=o(A’)< Thesesearchproblemsareimportantbutlimited in scope.
m a x A ’ ( V ) < m o ( V , R , Q ) = m a x A ( V ) . ThusA‘isanelement Important existing and potential problemsdo notuse distance
ofF(V,R,Q)ando(Y,R,P)<o(A’)=m,(V,R),acontradic- separation to mitigate interference. For example, fixed dis-
tion. By Theorem 29, m o ( V , R , Q)<m o ( V , R ) . Now, let A tance separation plays no role if the transmitters are mobile,
be an element of F( V , R, 9 ) such that o ( A ) = o ( V , R , 9). By if the transmitters are colocated, or if the distance between
what has already been shown, we have o ( V , R,2) = m c( V , R). transmitters is insignificant. In this section, we developan
Therefore A is an elementof F( V , R , 9 ) C F( V , R ) and o ( A ) = approach to channel assignment problems for this more com-
m , ( V , R ) . Bydefinition,mo(V,R)4maxA(V)=mo(V,R,Q). plex situation. In particular, we model frerlnency constrained
Q.E.D. channel assignment problems (both minimum span and mini-
mum order) as search problems; we show that these search
I. A Summary of the Theory problemsextendthesearchproblemsofSection III to this
At the beginning of this section, we promised to investigate more complex situation; and for these more general problems
the cochannel, minimum span, and minimum-order assignmentwe indicate how to develop a theory that parallels the theory
problems, and to develop a theory which would illuminate the of Section 111.
relationships among these problems. We have shown that the
cochannel assignment problem plays a central role and serves A . The Problems: F-CCAP, F-CAP, F-CAPOL, and F-CAPO
to tie the other two problems together. In particular, we have In each of the papers [8] -[ 101, [ 171 a frequency separation
demonstrated that: all of the search problems consideredin matrix serves as a set of interference limiting constraints. To
this section (i.e., F*D-CAP, F*D-CAPOL, F*D-CAPO, and all illustrate, if V = { 1 , 2 , -- ,n } denotes a set of transmitters
subproblems of these) have algorithmic solutions (Theorems and t (i, j ) is the set of forbidden channel separations fortrans-
2, 8, 10, and 23); if one is interested in merely minimizing the mitters i and j , then the nxn matrix [t(i, j ) ] is a convenient
span of an assignment, then m ( V , R) channels will suffice and way to display and/or store these forbidden channel separa-
if any more are allocated they arewasted (Theorem 7); a mini- tions (see Example Five below for concrete illustrations). A
mum span assignment may tie up more channels than neces- matrix such as [ t (i, j ) ] is a natural way to model interference
sary (Examples One and Two); a minimum-order assignment limiting constraints which employ only frequency separation
(bandwidth limited or not) never ties up more channels than to mitigate potential intereference (e.g., if the transmitters to
does a minimum span assignment and may tie up fewer chan- which channels must be assigned are colocated, the distance
nels (Theorem 28, Examples One and Two); a minimum-order separations are small enough to be insienificant or the trans-
assignment ties up at least m, ( V , R ) (the number of channels mitters are mobile). We now formalize such a matrix approach
tied up by an optimal assignment for the cochannel subprob- to frequency constrained channel assignment problems.
lem) channelsandpossiblymore (Theorem 16 and Example Let P*(Z,’) = {SCZ,’iS is empty or S is finite and 0 is an
Two); as the number of channels available for assignment in- elementofS},andletV={1,2,---,n). I f t : V X Y+P*(Z,’)
creases from m ( V , R) to m o ( V , R) the number of channels satisfies t ( i , j ) = t ( j , i ) and t(i, i ) = { } for all i and j in Y,
tied up by a minimum-order assignment decreases from m ( V , then t is called a channel separation matrix forV. If A : V + Z+
R ) to m,( V , R ) (Theorem 30); if one is interested in mini- satisfies
mizing the order of an assignment, then m o ( V , R ) channels
I A ( i ) - A ( j ) l doesnotbelongto t(i,j), foralliandjin V
wiU sufficeand if anymoreareallocatedtheyare wasted
(1) and 22span
minimum-order
(Theorems and
minimum
3 1); the
HALE: FREQUENCYASSIGNMENT 1505

then A is called a feasible assignment for Vandt . The elements F- CAPO

of V may be thought of as names for a set of n transmitters. INSTANCE: t a channel separation matrix for V.
Thus (1) requires that transmitters i and j not be assigned to FIND: A minimum-order assignment for V and t .
channels with forbidden channel separations. If t is a channel
separation matrix for V , then define t , : V X V +P*(Zi) by
B. Frequency Constrained Problems Generalize F*D

t , (i,i ) =
I the empty setif t(i,j ) is empty
{ 0) if t ( i ,j ) is not empty.
Constrained Problems

The problems F-CCAP, F-CAP, F-CAPOL, and F-CAPO are

calledfrequencyconstrainedproblemssince superficially, at
Clearly, t , is a channel separation matrix for V , and if t ‘ is
any channel separation matrix for V such that t’(i, j ) C t ( i , j ) least, they employ only frequency separationt o mitigate inter-
for each i and j in V , then t J i , j ) C t’(i, j ) for each i and j in ference. We now show that any set of F*D constraints may be
V. Also, if A is a feasible assignment for V and t,, then (1) replacedbyanequivalentchannelseparation matrix, and
requires that A ( i ) # A ( j ) whenever t c ( i ,j ) = {O}. Therefore, therefore the problems of this section contain the correspond-
t , is called t’s cochannel submatrix. ing problems of SectionI11 as subproblems.
If t is a channel separation matrix for V , then let F ( V , t ) Let V = { u l , * , u,} be a subset of the plane and let R =
denotetheset of all feasibleassignmentsfor V and t . Let { ( T ( i ) , d ( i ) ) [=
i 0, , m } beaset of F*Dconstraints.Let
m ( V , t ) denote min { m a x A ( V ) I A is an element of F ( V , t ) } . -
V’ = { 1, * , n } and define t ’ : V‘ X V’ + P*(Z,’) as follows:
If A is an element of F ( Vt,) , and max A ( V ) = m ( V , t , ) , then if i # j and k is the smallest integer for which D(ui, ui) < d ( k ) ,
A is called an optimal assignment for Vand t,. We now formu- then t’(i,j ) = T ( k ) and otherwise t’(i,j) equals the empty set.
late the frequency constrained cochannel assignment problem. If A : V + Z + , then define A ’ : V’ Z+ by A‘(i) = A ( q ) for
-
--f

i = 1, * ,n.
Theorem 32: A is feasible for V and R if and only if A’ is
F- CCAP feasible for V’ and t ’.
INSTANCE: t a channel separation matrix for V = { 1, * * , Proof: Suppose A is feasible for V and R . Case 1: if ui #
.I. ui and k is the smallest integer for which D(ui, ui) Q d ( k ) then
FIND: An optimal assignment for V and t,. IA’(i) - ~ ’ ( j ) l =I A ( U -~ A) ( u ~ is) ~not an element of ~ ( k=)
t‘(i, j ) . Case 2: otherwise ] A ‘ ( i )- A ’ ( j ) l is not an element of
If A is an element of F ( V , t ) and max A ( V )= m ( V , t ) then { } = t ( i ,j ) . Therefore A’ is feasible for V’ and t’. Conversely,
A is called a minimum span assignment for V and t . We now suppose IA’(i) - A ‘ ( j ) l is not an element of t‘(i, j ) for all i
formulatethe frequency constrained minimum spanassign- and j in V ’ . Also, suppose ui # uj and D(ui, vi) Q d ( Q ) . Now
ment problem. i # j and if k is the smallest integer for which D(ui, ui) < d(k),
then t’(i, j ) = T ( k )and IA(ui) - A(ui)l = IA‘(i) - A ‘ ( j ) l is not
F- CAP an element of t‘(i, j ) = T ( k ) C T ( Q ) . Therefore, A is feasible
INSTANCE: t a channel separation matrix for V. for V and R . Q.E.D.
FIND: A minimum span assignment for V and t . Example Five: F-ACAP, F-ACAPOL, and F-ACAPO and the
subproblems of F-CAP, F-CAPOL and F-CAPO, respectively
If Q > m ( V , t ) then, letF ( V , r , Q)denote { A 1A is an element obtained by restricting t ( i , j ) t o be an element of {{ }, {0},
of F( V , t ) and max A ( V ) Q a}; let o ( V , t , Q)denote min (0, 1)). F-UHF, F-UHFOL, and F-UHF0 are the subproblems
(0( A ) [ is A an element of F ( V ,t , 2)); and let mo ( V , t , 9) de- of F-CAP, F-CAPOL, and F-CAPO, respectively obtained by
note min {max A ( V ) I A is an element of F ( V , t , n) and o ( A ) = restricting t ( i , j ) to be an element of {{ }, {0}, ( 0 , 15}, (0,
o ( V , t , Q ) } . IfAisanelementofF(V,t,Q),o(A)=o(V,t,Q), 7, 14, 15}, (0,1,7,14,15}, (0,1 , 2 , 3 , 4 , 5 , 7 , 8 , 14,15}}.
m a x A ( V ) = m o ( V , t , Q), and L = { l , 2 , . * . , Q } , then A is We have the followingresults as immediatecorollaries of
called a minimum-order assignment for V and t and in L . We Theorem 32.
now formulatethe frequency constrainedminimum-order Theorem 33: F*D-CCAP, F*D-CAP, F*D-CAPOL, and
assignment problem (with limited bandwidth). F*DCAPO are subproblems of F-CCAP,F-CAP,F-CAPOL,
and F-CAPO, respectively.
Theorem 34: F*D-ACAP, F*D-ACAPOL, and F*D-ACAPO
F- CAPOL aresubproblems of F-ACAP, F-ACAPOL andF-ACAPO, re-
INSTANCE: t a channel separation matrix for V and Q 2 spectively.
m (V,t). Theorem 35: F*D-UHF, F*D-UHFOL, and F*D-UHF0 are
FIND: Aminimum-orderassignmentfor V and r in L = subproblems of F-UHF, F-UHFOL, and F-UHFO, respectively.
-
(1, * * , 2). In Section VII, we will see that the converses of Theorems
33, 34, and 35 are not valid. Thus the frequency constrained
Let m , ( V , t ) denote m ( V , t,). If A is an element of F( V , t ) matrix approach of this section is more general than the F*D
and o ( A ) = m,(V, t ) then A is called a minimum-order assign- approach of Section 111. Inaddition,thematrixapproach
ment for V and t . Let F o ( V , t ) denote the set of all such obscurestheroleplayed by distanceseparationand in this
assignments. The integer min { max A ( V ) I A belongs to Fo ( V , respect may hide (or encode) potentially useful information.
t ) } is called the minimum span o f a minimum-order feasible In particular, efficient solutions for some important subprob-
assignment for V and t and is denoted m o ( V , t ) . If A is an lems of F-CAP require that this encoded distance separation
elementofFo(V,t)andmaxA(V)=mo(V,t),thenAiscalled information be decoded. From this point of view F*D formu-
a minimum-orderassignment for V and t. We nowformu- lations of problems are more desirable. (This important point
latethe frequency constrainedminimum-orderassignment will be discussed at greater length in Section VII.)
problem. The reader may easily verify that Theorems 1-31 of Section
1 SO6 PROCEEDINGS OF THE IEEE, VOL. 68, NO. 12, DECEMBER 1980

I11 remain valid if F*D and R are replaced in every occurrence

by F and t , respectively. It may be beneficial to reread the
summary at the end of Section I11 with this transformation in
mind. d j k ( i ) = (dii(i)+ dkk(i))/2, for j , k = 1, - - ,p
*

V. OTHERPROBLEMS and i = O , - - - , m .
The main purpose of this paperis to provide a unifying theory Clearly, (01= T j k ( O ) c Tjk(1) * c --c Tik(m) and
which demonstratesthatourformalmodelingapproachto
assignment problems is a viable one that can handle the wide djk(O)>djk(l)>..'>dik(m)>o .
range of problems which arise (or may arise) in the real world.
Up until now, we have restricted our attention to situations in Therefore, let R = {(Tjk (i), djk(i))lj, k = 1, --
,p and i =
which assignments are confined to discrete evenly spaced fre- 0, - m } be called a set of F*D constraints for the mixed
e ,

quencies. As we shallsee, our formalmodelingapproach is service V = { V i , V ,, -- ,Vp}. Thefollowing search problem

not limited to such problems. is anatural extension of F*D-CAP to this morecomplex
Supposetherearetwoormore classes of transmitters Ci situation.
where all the transmitters in Ci have the same operating power
Pi and the same operating bandwidthbi but that Pi #Pi and/or F*D-CAP(*)
bi # bi for i # j . In addition, suppose thatideally all the trans- INSTANCE: V is a finite subset of the plane, p < I VI, and
mitters should be assigned to operating frequencies in the
region of the spectrum. Results of Section I11 (e.g., Examples
same R a set of F*D constraints for the mixed service { V I , ---
,V p } .
FIND: A : V + 2' which satisfies (7) and IA ( u ) - A (u)l is
One and Two, and Theorems29,30, and 31) suggest that spec- not an element of Tjk(i) whenever u # v, u is an element of
trum may be conserved if these different classes were to share 5, u is an element of Vk, and
the same band in an interwoven fashion. In this section, we
investigate F*D and frequencyconstrainedassignmentprob-
lems that model this potentiallyuseful interwoven approach to
D ( u , u ) < djk(i), ---
for j , k = 1, --
,p and i = 0, -,m. (9)
spectrum sharing. Two of theseproblems are notchannel An assignment A : V + 2' which satisfies (7) and (9)is called
assignmentproblems,i.e.,assignments are notrestrictedto a minimum span assignment for V and R . We must remark
discrete frequencies. We conclude this section with a discus- that the search problems F*D-CAPOL(*) and F*D-CAPO(*)
sion of other well-known assignment problems that are not in which we search for minimum-order assignments forV and
channel or frequency assignment problems and note that some R in L and minimum-orderassignmentsfor V and R (with
of these problems appear to be closely related to frequency obvious definitions), respectively, have the expected interrela-
assignment problems. tionshipswith F*D-CCAP(*) and F*D-CAP(*). That is,
Theorems 1-31, and analogs to Theorems 32,33, and 34, and
A. Interwoven Mixed Service with Variable Power 35 remain valid for these problems. (Hint: if i # j , vi is an ele-
Transmitters ment of V k , ui is an element of VQ and h is the smallest integer
-
For i = 1, * ,p , let Vi denote the set of locations ofall for which D(ui,. u i ) < dkp ( h ) then define t'(i, j ) = T ~( hQ) and
transmitters having power Pi and let di denote the cochannel otherwise rf(i,1 ) = { }). In Section W, we will see that the
separation distance for a pair of transmitters in Vi. The fol- converses of Theorems 33, 34, and 35 are not valid for these
lowing search problem is a natural extension ofF*D-CCAP to problems.
this more complex variable power situation.
B. Interwoven Mixed Service With Unevenly Spaced Dirczete
F*D-CCAP(*) Frequencies
INSTANCE: V a finite subset of the plane, p I VI, { V I ,< F o r i = l ; * . , p , l e t Vi,PiandRbeasinthelastparagraph,
V,, * * * , V p } a partition of V , and di an element of Q' for and let all the transmitters in Vi have operating bandwidth bi
..
i = 1 , . , P. belonging to ' Q with bi # bi wheni # j . Let B = { b l , ---
,bp}.
FIND: A : V + 2' which satisfies the conditions: Now, in addition to allowing these different classes of trans-
max A ( V ) is as small as possible (7) mitters to share the same band in an interwoven fashion also
allow frequencies t o be assigned to any element of C f ( B )=
and {kbi/2li=l;..,p;k=1,3,5;..}.
IA ( u ) - A ( u ) J> 0 whenever u # u, u is an element of Vi, As motivation for this approach, consider that, in practice,
u is anelement of Vi and D ( u , u ) < (di + di)/2. (8) many F*D constraintsresult from the factthat asigning trans-
mitters to discrete evenly spacedfrequencies increases the
More generally, if Vi and Pi are as above, let Ri = {(Ti(i), potential for intolerable interference[ 821. Intuition leads one
di(i))(i= 0 , . * , m } be a set of F*D constraints for transmit- to believe, therefore, that spectrum may be conserved by al-
tersin Vi. Let m = m a x { m i l j = l ; - . , p } andfor j , k = l , lowing transmitters to be assigned to unevenly spaced frequen-
*- * , p d e f i e d Tjk and djk as follows:
cies. In order, not to violate our convention that search prob-
lem assignments have the form A :Y + Z + , let us rename the
elements of C'(B). That is, if bi = rJsi, then let lcm be the
leastcommonmultipleof2,sl;--,sp,andfori=1;--,p
- ,p - - - - - sp is even
T'k ( i )= Tii(i) union Tkk(i), for j , k = 1,
and i = O ; * * , m
let ri =
I 1cm rilsi,
-
1cm 512 - si,
if s1 s2
otherwise.
HALE: FREQUENCY ASSIGNMENT 1507

NowletC(B)={l+kr~li=l,...,p;k=O,1,2,"'}CZ'. inf {max A ( V )IA is an element of F(I)}. If A is an element

The following search problem is a natural extension of F*D- of F(I) and max A ( V )= rn (I) then A is called a minimum
CAP(*) to this situation. span assignment for I. The following optimization problem is
called thefrequency-distanceconstrainedfrequency assign-
F*D-CAP(*; *) ment problem.
INSTANCE: V a finite subset of the plane, p < I VI, R a set
of F*Dconstraintsforthe mixed service { V I , - , V p } , and F*D-FAP
-
B = { b l , * * , bp} C Q '. INSTANCE: I = (V, P, B , T, s)
FIND: A : V +. C ( B ) which satisfies ( 7 ) and l/rh IA(u) - FIND: A minimum span assignment for I .
A(u)l is not an element of Tik(i) whenever u # u, u is an ele-
ment of Vi, u is an element of Vk, and D(u, u ) Qdik(i) for We now formulate a frequency constrained generalization of
j,k,II=l;..,pandi=O;..,m. -
(10) F*DFAP. Let V = { 1, * , n} be a set of transmitters, [s(i,j ) ]
be a symmetric nxn matrix where s(i, j ) is a nonnegative ra-
If A : V C ( B ) satisfies (7) and (10) then A is called a mini- tional number that denotes theminimum frequency separation
--f

mum span assignment for V , R,and B . Condition (10)requires required of transmitters i and j , and let [t(i,j ) ] be asymmetric
that u and u not be assigned to certainfrequencies (namely nxn matrix where t(i, j ) (an element of P * ( Z ' ) ) represents
those whose differences divided by r i belonp to Tjk(i))when the set of forbidden combinations of frequency assignments
u and u are separated byless than the minimum separation for i and j . In practice s(i, j ) and t(i, j ) may be functions of
distance required by R. In particular, if R is restricted to have D(i, j ) , the terrain surrounding i and j , the powers Pi and Pi of
the form {(Tjk(O), djk(O))(j , k = 1, * * * , p } , then the resulting i and j , the bandwidths bi and bj of i and j , the rejection char-
subproblem is denoted F*D-CCAP(* ; *), since in this case acteristics of receivers that tune to i and j , etc. We require that
only cochannel assignments are constrained. The reader may s(i, i)= 0 and that t(i, j ) = { } iff s(i, j ) = 0 for all i and j ele-
define F*D-CAPOL(*; *) and F*D-CAPO(*; *), and verify m e n t s o f r L e t B = { b l ; * * , b , } , b = m i n { b i / 2 l i = 1 ; * * , n )
that propositions analogous to Theorems 1-35 remain valid for and I = ( V ,B , t , s).
these problems. If A : V + [b, 00) satisfies: A(u) is in Q for all u in V with
A(u)<maxA(V),IA(i)-A(j)l>s(i, j ) andmax{A(i)/
C. Interwoven Mixed Service With No Resm'ction to A ( j ) , A (j)/A (i)} is not an element of t(i, j ) for all i and j in
Discrete Frequencies V , then A is called a feasible assignment for I. Let F ( I ) denote
Let V be a set of locations of transmitters. Let I VI = n , p Q the class of all such assignments and for q in Q' and let F(I, q)
n , a n d P = { V 1 ; . - , V p ) beapartitionof V. F o r i = I ; - * , p denote { A I A is an element of F ( I ) and maxA ( V ) < q}. Now
let Pi, and bi denote respectively theoperatingpowerand F(I, q) C F ( I ) and if A : V + [b, 00)is defined by A (1) = b and
--
bandwidth of transmitters in Vi where Pi #Pi and/or bi # bi for i = 2, * , n, A(i) = (qi + l/ni)/A(i - 1) (where qi = A(i -
whenever i # j . If u is an element ofVi, and u is an element of 1) + s(i, i - l), and ni is the smallest element of ' 2 such that
Vk, then let +(x) denote the minimum frequency separation (qi + l/ni)/A(i - 1) is not an element of t ( i - 1, i)), then A is
required for assignments to u and u when x = D ( u , u ) ; let an element of F(1, q ) when 4 > rnax A ( V ) . Therefore, let
Tjk(x) denote the forbidden combinations of frequency as- m ( I ) denote i n f {max A ( V )IA is an element of F(I)}. If A is
signments for u and u when x = D(u, u ) ; and let djk denote the an element of F(I) and rnax A ( V )= m ( I ) , then A is called a
cofrequency distance separation required of u and u. In prac- minimum span assignment for I. The following optimization
tice, Sjk and Tik may be functions of Pi, Pk, bi, bk, therejec- problem is called the frequency constrained frequency assign-
tion characteristics of receivers that tune to transmittersin ment problem.
Vj and Vk, etc. Ifmjk and mjk denote respectively the min F-FAP
and max of {D(u, u)l u is in Vi and u is in Vk}, then Sjk: INSTANCE: I = ( V , B , t , s)
[mjk,mjklQ [o, Sjk(mik)lQand
--f Tjk: [mjk,MiklQ FIND: A minimum span assignment for I .
P*(Z')where we, also, requlrethatD(u, u ) = 0 iffu = u ;
Sjk(X) = 0 and Tjk(X) = 0 iff djk < X < mjk Or j = k and X = 0 ; The reader may define m c ( I ) , o ( I , q), m o ( I , q ) , mo(Z), F*D-
and if X > y then sjk(X) < s & ) and Tjk(X) c Tjk(Y). Let CFAP, F*D-FAPOL, F*D-FAPO, F-CFAP, F-FAPOL, F-FAPO
B = { b 1 , * * * , b P } ,b = m i n h i / 2 l i = l ; * . , p } ,S = { s j k l j , and verify that Theorems 1-35 (excepting 2, 8, 10, and 23)
k = l ; * - , p } , T = { T j k l j , k = l ; * * , p } a n d I = ( I . ' , P , B , T , remain valid. The decidability of F*D-CFAP,F-CFAP,etc.,
SI. are left as exercises for complexity theorists.
If A : V + [ b , 00)satisfies: A ( u ) is an element of Q for all u
with A(u)<maxA(V), I A ( u ) - A(u)I>Sjk(D(u, u)), and D. Other Combinatorial Optimization Problems
max { A ( u ) / A ( u ) ,A(u)/A (u)} is not an element of Tjk(D(u, The assignment problems of this paper are special cases of a
v)) whenever 11 # v, 11 is in and u is in Vk, then A 1s called more general assignment problem. Given a collection of con-
a feasible assignment for I . Let F(Z) denote the set ofall such sumers who place demands upon a set of resources, find an
assignments and for q an element of ' Q let F(I, q) denote assignment of consumers to resources that satisfies various
{ A IA is an element of F ( I ) and max A ( V )< q } . Let u l , , constraints and that minimizes (or in some cases maximizes) a
u, be a list of V such that u1 is an element of Vi and b = bi/2. given objective function. The approach of this paper (i.e., the
If A : V + [b, 00)is defined by A ( u l ) = b and fori = 2, * , n, modeling of frequency assignment problems as searchprob-
A(ui) = (qi + l / n i ) A ( ~ i - ~ (where
) qi = A ( U ~ + - ~sjk(D(Ui-1,
) lems) has beeneffectivelyapplied to other problems of the
vi)), and ni is the smallest element of Z' such that (qi + l/ni)/ assignment type. To illustrate, in network routing problems,
A ( ~ i - ~is ) not an element of T ~ ~ ( D ( Uvi)), ~ - ~ui-l, is an ele- calls or packets areassigned to paths or Links of the network in
ment of Vj. and ui is an element of Vk), then A is an element such a way that the number of simultaneous calls through the
of F(I, 4) when q > A.(u,). Therefore,let m ( I ) denote network is maximized orthe average packetdelay is mini-
 1508 PROCEEDINGS OF THE IEEE,VOL. 68, NO. 12, DECEMBER 1980

mized; in school timetabling problems, instructional units are

assigned to time periods, teachers, rooms, instructional equip-
ment,orotherresourcesinsucha way thattheconsumed
resource(s) is minimized;incomputer job schedulingprob-
lems, jobs to be executed are assigned to starting times and
processors in sucha way that the earliest time at whichall jobs
are completed is minimized; and in the graph coloring prob-
lem, vertices are assigned colors in such a way that adjacent
vertices are assigned different colors and the number of colors
used is minimized. ' t
80
We have not investigated frequency assignment problems in
which the spectrum is time shared, but must remark that these
problems appear tobe closely related to theextensively studied
t
"I
computer job scheduling problems [ 831 -[88] .
It is well known that the graph coloring problem is closely
related to the cochannel assignment problem[ 51, [ 111, [ 121,
1131 and to school timetabling problems [501, [511, [531. In 20
thenextthree sections, we extendandexploittheformer
relationship. 0 20 40 60 W 100 EO
Fig. 3. Graphical depiction of the set of transmitterlocations, the taboo
VI. GENERALIZED
COLORINGPROBLEMS combinations of channel d g n m en s
t,the minimum span assignment
A and the minimum-order sssignment B of Example Three.
Thepapers [ 101, [ 121, [ 131 discuss therelationship of
F*D-CCAP to the following search problemcalled the coloring
problem (CP). GCPOL
INSTANCE: G = ( V , E ) , t an edge constraint forC , and L =
CP {l;..,Q}whereX1(G,t)(B .
INSTANCE: G = ( V , E ) a graph. FIND: A minimum-order coloring for G and t in L.
FIND: A : V + Z+ such that maxA ( V ) is as small as possible
and A ( u ) # A ( u ) whenever uu is an element of E (such an as- Let C = ( V , E ) and define c : E + P ( Z ; ) by c(uu) = ( 0 ) for
signment is called an optimal coloring for G , max A ( V ) is all uu in E. Clearly, c is an edge constraint forG and if t is any
called the chromatic number o f C and is denoted X ( G ) ) . edge constraint for G then c(uu) C t(uu) for a l l uu in E. There-
fore, c is called theminimaledgeconstraint f o r G , and by
If G = ( V , E ) is a graph and t : E P(Z,') then t is called an
--f
definition x 1 ( G , c=) X ( G ) . Also, as in Section III Theorem
edge constraint f o r C and G , = ( G , t ) is called an edge con- 16, X ( G ) < o ( A ) forany A in F ( G , t). Thus min {max
strained graph. If A : V --* Z+ satisfies [ A( u ) - A (u)l is not an A ( V )[ A is an element ofF(G, t ) and o ( A ) = X ( C ) } is denoted
element of t ( u u ) whenever uu is an element of E, then A is X 2 ( G , t ) and is called the minimum order chromatic number
called a feasible coloring for G and t. Let F ( G , t ) denote the for G and t . If A is an element of F(G, t), o ( A ) = X ( C ) and
class of all such colorings, and let X l ( G , t ) denote min {max max A ( V ) = X 2 ( C , t ) then A is called a minimum-order color-
A ( V ) I A is anelement of F ( G , t ) } . If A is anelement of ing f o r G and t . The following search problem extends the
F ( G , t ) and max A ( V ) = X1( G , t ) , then A is called a minimum notion of minimum order assignment (with unlimited band-
span coloring for G and t . The integer Xl(G,t ) is called the width) to graph coloring.
minimum span chromatic number for G and t .
The following search problem extends CP to edge constrained GCPO
graphs and is called the generalized coloring problem. INSTANCE: G = ( V , E ) and t an edge constraint forG .
FIND: A minimum-order coloring for G and t.
G CP
INSTANCE: G = ( V , E ) , and an edge constraint for G . Example Six: Fig. 3ofSection III depictsan edge con-
FIND: A minimum span coloring for G and t . strained graph generated by the UHF taboos and the set of
transmitterlocations V of Example Three. The t(uiuj)'s in
If A is an element of F ( G , t ) , then [ A( V ) l is called the order Fig. 3 are the values of the edge constraint imposed by the
of A and is denoted o ( A ) . If Q is an element of Z+, and 9 2 UHF taboos. Similarly, F@. 1 and 2 depict edge constrained
X1(G, t ) , then let F ( G , t , 2) denote { A [ A is an element of graphs generated by instances of F*D-ACAP. In addition, the
F(G,t)andmaxA(V)<i?),leto(G,t,Q)denotemin{o(A)[A minimumspan(minimum-order)assignmentsillustrated in
is an element of (G, t , Q)},and let X 2 ( G , t , 9 ) denote min {max these figures are minimum span (minimum-order) colorings for
A(V)IAisinF(G,t,Q)ando(A)=o(G,t,Q)}.I f L = { l ; * - , the correspondingedge constrained graphs.
Q), then X z ( G , t , 9 ) is called the minimum-order chromatic By the definitions, if ?! > X ( C ) , then X ( C ) = o ( C , c, !?)=
number for G and t in L . If A is an element of F ( G , t, Q), X1(G,c)=X2(G,c,~)=Xz(G,c)andthereadermayverify
o(A)=o(G,t,8)andmaxA(V)=X2(G,t,!?),thenAiscalled that Theorems 1-3 1 and their proofs remain valid.8V,R , m,,
aminimum-ordercoloringforG and t in L. Thefollowing m , m o F*D-CCAP,
, F*DCAP, F*D-CAPOL, andF*D-CAPOL
search problem extends the notion of bandwidth limited mini- are replaced in every instance by G , t, X,XI, X , , CP, GCP,
mum-order assignment to graph coloring. GCPOL, and GCPO, respectively.
HALE: FREQUENCY ASSIGNMENT 1S O 9

Let G and t be as above and let C C Z’. If A : V C satisfies --f and arigorous treatment of these matters. In addition, the
IA ( u ) - A (u)l is not an element t (uu) for all uu in E then A paper [24] presents anexpository discussion of these mat-
is called a feasible coloring for G , t , and C. Let F ( G , t , C) ters.) Using recent results on the computational complexityof
denote the class of all such colorings, and let X1(G, t , C) de- graphcoloring togetherwiththe equivalences between fre-
note min {max A ( V ) I A is an element F ( G , t , C)}. If A is quency assignment problemsand generalized graphcoloring
an element of F ( G , t , C) and max A ( V ) = X1(G, t , C), then A problems, we show that each of the assignment problems of
is called a minimum span coloring f o r G , T and C. The fol- Sections 111, IV, and V is NP-hard, but that some important
lowingsearch problem extends GCP to the situation of un- subproblems of these problems have efficient solutions.
evenly spaced colors.
A. Frequency Constrained Problems and Their Complexity
GCP( *) It is well known that CP is NP-hard [ 201 and that F-CCAP is
INSTANCE: G = ( V , E ) , t an edge constraintfor G, and related to CP [ l o ] . In this paragraph, we show that F-CCAP,
c c Z+. F-CAP,F-CAPOL,F-CAPO, F-CCAP(*; *), F-CAP(*; *),
FIND: A minimum span coloring for G, t , and C. F-CAPOL(*; *), F-CAPO(*; *), F-CFAP, F-FAP,F-FAPOL
and F-FAPO are equivalent to CP, GCP, GCPOL, GCPO,
If t : E + P(Z,’) is an edge constraint for G = ( V , E), and CP(*), GCP(*), GCPOL(*), GCPO(*), CP(*; *), GCP(*, *),
s :E + Q’, then ( V ,E, t , s) is denoted G , and is calleda doubly GCPOL(*; *), andGCPO(*; *), respectively. From these
edge constrained graph. If A : V + R + satisfies: A ( u ) is an ele- equivalences and the NP-hardness of CP it follows that each of
ment of Q’ for all u in of V such that A ( u ) < max A ( V ) , the twelve frequency constrainedproblems listed above is
1.4 ( u ) - A(u)I 2 s(11u) and max { A ( u ) / A( u ) , A ( u ) / A( u ) } is not NP-hard.
an element of t(uu) for all uu in E , then A is called (I feasible Theorem 36: F-CCAP is equivalent to CP.
coloring f o r G, t and s. Let F ( G , t , s) denote the class of all Proof: If V = { 1, * , n } and t , is an instance of F-CCAP
such colorings and X I ( G , t , s) denote inf {maxA(V)IA is an thenlet E = { i j I t , ( i , j ) # { }}. N o w G = ( V , E ) i s a n i n s t a n c e
element of F ( G , t , s)}. If A is an element of F ( G , t , s) and of CP and A : V + { 1, * * ,X ( G ) } an optimal coloring for G is
maxA(V)=X1(G, t , s), then A is called aminimum span also an optimal assignment for V and t , with m ( V , t , ) = X ( G ) .
coloring f o r G , t and s. The following optimization problem Conversely, if G = ( V , E ) is an instance of CP where V = { u l ,
extends GCP to the situation in which there is a nondiscrete . - . , u , } t h e n l e t V ’ = { l , * * - , n } a n d d e f i n e
set of allowable colors.

GCP(*; *)
INSTANCE: G = ( V , E ) , t : E + P ( Z i ) , and s : E + Q’ Now V’ and t , is an instance of F-CCAP and if A ‘ : V‘ +
FIND: A minimum span coloring for C , t and s. * , rn (V’, t,)} is an optimal assignment for V’ and t,,
{ 1, *
then A : V + Z ’ defined A ( u i ) = A ( i ) for all i = l ; - . , n is
The readermaydefine CP(*), GCPOL(*) and verify that anoptimal coloring for C and X(C) = m ( V , t,). Q.E.D.
theorems analogous to Theorems -1-3 1 remain valid for these Theorem 37: F-CAP, F-CAPOL, and F-CAPO are equiva-
problems. Similarly, analog to Theorems 1-3 1 (excepting the lent to GCP, GCPOL, and GCPO, respectively.
proofsfor2, 8, 10, and 23) remain valid for the problems Proof: If V = { l ; - - , n } , t and 1 is an instance of F-
C(*; *), GCP(*; *), GCPOL(*; *) and GCPO(*; *). CAPOL, then let E = { i j l t ( i , j ) # the empty set} and continue
the
as in proof of Theorem
36. Q.E.D.
VII. ASSIGNMENTPROBLEMS AS GENERALIZED Theorem 38: F-CCAP(*; *) is equivalent to CP(*).
COLORINGPROBLEMS Proof: I f V = { 1 ; . * , n } , t , , a n d C C Z + i s a n i n s t a n c e o f
An important element of the scientific approach to problem F-CCAP(*; *), then let E = { i j I t , ( i , j ) # the empty set}. Now
solving consists of attempting t o show that the problem under G = ( V , E ) and C is an instance of CP(*). Continue as in the
study is closely related to a known, well-studied problem. In proof 36. of Theorem Q.E.D.
this section, we show that each of the frequency constrained Theorem 39: F-CAP(*; *), F-CAPOL(*; *), and FCAPO(*;
problems of Sections IV and V is equivalent to a generalized *) are equivalent to GCP( *), GCPOL(*) and GCPO(*), respec-
graph coloring problem and that each of the F*D constrained tively.
problems of Sections I11 and V is equivalent to a generalized Proof: If V = { l ; * * , n } , t a n d C C Z + i s a n i n s t a n c e o f
coloring problem restricted to a narrow subclass of the class F-CAP(*; *), then let E = { i j l t ( i , j ) # the empty set} and
of all graphs. From these results, it follows that the frequency define t ‘ :E P(Z,’) by t ’ ( i j ) = t ( i , j ) for all ij in E. Now G =
--f

constrainedapproach is more general thanthefrequency- ( V , E ) , t‘ and Cis aninstance of GCP(*),etc. Q.E.D.

distance constrained approach to assignment problems. Theorem 40: F-CFAP is equivalent to CP(*; *).
Recent developments in the theory of computational com- Proof: If V = { 1, * * * ,n } , t,, and S, is an instance of
plexity allow for the c1assificatic.n of optimization problems F-CFAP, then let E = {ijlt,(i, j ) # the empty set} and define
according to the“executiontime efficiency” of algorithms t‘ :E + P(Z,’), S‘ :E + Q’ by t ‘ ( i j ) = t , ( i , j ) = { l}, s ’ ( i j ) =
that may be devised for their solution. Informally, if an opti- S, (i, j ) for ij in E . Now G = ( V , E ) , t’ and s‘ is an instanceof
mization problem is NP-hard, then it is very unlikely that a CP(*; *), etc. Q.E.D.
polynomialtimesolution will ever be devised. (The reader Theorem 41: F-FAP, F-FAPOL, and F-FAPO are equivalent
who is unfamiliar with the concept of NP-hardness and who to GCP(*; *), GCPOL(*; *) and GCPO(*; *),respectively.
would like more information on what is meant by “very un- Proof: If V={l;.-,n},t,andsisaninstanceofF-FAP,
likely’’ is referred to 1231 for both a low-level introductory then let E = { i j l t ( i , j ) # the empty set} and define t’ : E +
 1510 PROCEEDINGS OF THE IEEE, VOL. 68, NO. 12, DECEMBER 1980

as in Section V-B, then let E = {uulu # u, u is an element of

V . , u is an element of V, and D(u, u ) < d-k(O),j , R = 1, * * * ,
p{ and define t : E +P(Z,') by t (uu) = { h r i l n = 1, --- ,p ; h is
in T j k ( i ) where u is in Vi, u is in V, and i is the largest inte-
ger for which D ( u , u ) < d j k ( i ) } . Now G = ( V , E ) , r and C ( B )
is an instance of GCP and A :V + C(B) a minimum span color-
ing for G,t and C ( B ) is also a minimum span assignment for
V , P, R , and B. Q.E.D.
For future reference, the edge constrained graphG , = ( V , E ,

u u t ) in the proof above is denoted G , [ I ] and is called the edge

constrained graph generated by I = ( V , P , R , B). Let C,[ *; * ]
denote the class of all such graphs, let G,[*] denote the sub-

*
Fig. 4. A unit disk graph together with one of its intersection models.
- -
class that results when bi = b for i = i , * ,p . (Note: in this
case, r h = 1 for P = l , - - - , pand C ( B ) = Z + so G,[*]is the
class of edge constrainedgraphs generatedby instances of
t F*D-CAP(*)), let G,[ p ; p ] and G , [ p ] denote the subclasses
that result when p is f i e d . (Note: G, 111 is the class of edge
K (1,6): constrained graphs generated by instances of F*D-CAP.)
Theorem 44: F*DFAP is equivalent to a subproblem of
GcP(*; *).
R o o f : If I = ( V , P , B , T , S, d ) is an instance of F*D-FAF',
thenlet E = { u u l u # u , u i s i n V.,uisin V k , D ( u , u ) < d j k j ,
k = l ; * . , p } . Definet:E+P(.?!,')ands':E+Q+byt(uv)=
Tjk ( D ( u , u ) ) and ~ ' ( u u=) sjk(D(u, u ) ) when u is in Vi,u is
in V k , a n d j , k = l ; - - , p . NowC=(V,E),tands'isanin-
Fig. 5. The six pointed star K ( 1 , 6) and other graphs that are not unit stance of GCP(*; *) and if A : V + R + is a minimum span
disk graphs.
coloring for G,t and s f , min A ( V ) = q' (anelement of Q') and
q = b/q' then A : V + [ b , m) defined A'(u) = q A ( u ) for all u in
V is a minimum span assignment for I . Suppose, to the con-
P(Z,'),s f : E + 'Q by t ' ( i j ) = t ( i , j ) , s ' ( i j ) = s ( ij, ) for all ij in trary, that B is an element ofF ( I ) and rnax B( V )< rnax A ( V ) .
E. Now G = ( V , E ) , t', s' is an instanceof GCP(*; *), etc. Let e = max A ' ( V ) - rnax B ( V ) and let q f r belong to (0, e)Q
Q.E.D. such that 4" < l/q. Now A " : V+R+definedA"(u) = qr'A'(u)
Theorem 42: F-CCAP, F-CAP, F-CAPOL, F-CAPO, F- is a feasible coloring for G, t and sr such that max A " ( V ) <
CCAP(*; *), F-CAP(*; *), F-CAPOL(*; *), F-CAPO(*; *), max A ( V ) which is impossible. Q.E.D.
F-CFAP, F-FAP, F-FAPOL, and F-FAPO are NP-hard. Forfuture reference, thedoubly edge constrained graph
Proof: It is well known that CP is NP-hard and the theorem ( V , E, t , s f ) in the proofabove is denoted G , [ I ] and is
follows since F-CCAP is a subproblem of each of the others. called the doubly edge consfrained graph generate by I . Let
Q.E.D. G, [ *; *I denote the class of all such graphs. (Note: G,[ *; *]
is a proper subclass of G, [ *; *I). In order to classify the F*D
B. Frequency-Distance Constrained Problems and constrained problems as to their complexity, it is convenient
Their Complexity to first characterize the edge constrained graphs generated by
It is known that F*D-CCAP is related to CP [ 51, [ 121, [ 131, these problems. A closed disk in the planeis called a unit disk
andthatotherF*D constrainedproblemsareequivalent to if it has diameter one, and G = ( V , E ) is called a unit disk
generalized coloringproblems [89] . Inthis paragraph, we graph if it has an intersection model { D , Iu is in V } consisting
show that F*D-CCAP is equivalent to CP restricted to a narrow of unit disks in the plane (e.g., see Fig. 4). Let B1(2) denote
class of graphs called unit disk graphs. Similarly, we show that the class of all unit disk graphs. If G = ( V ,E ) belongs to B1(2),
each of the F*D constrained problems of Sections 111 and IV is { D , I u is in V } is an intersection model forG, and R = { ( T ( i ) ,
equivalent to a generalized coloringproblemrestricted -
to a d ( i ) )Ii = 0 , * ,m } is a set ofF*D constraints, thenlet
narrow class of edge constrainedgraphs called disk graphs. d '(i) = d ( i ) / d ( O )for i = 0,* ,m and let u' denote the center --
From these equivalences andtherecent discovery that CP of D , for each u in V . Define t : E +P(Z,') by t(uu) = T ( i )
restricted to unit disk graphs is NP-hard it follows that the F*D where i is the largest integer forwhich D(u', u ' ) < d ' ( i ) . Now
constrained problems of Sections I11 and IV are each NP-hard. G , = ( V , E, t ) is an edge constrained B l ( 2 ) graph generated by
Thus open questions concerning the complexity of F*D con- R . Let E r ( 2 ) denote the class of all edge constrained B1(2)
strained problems [891are resolved. Finally, thefrequency- graphs obtained in this way.
constrained approach is more general than the F*D approach Theorem 45: C,[ 11 =Bf(2).
since K ( 1, 6 ) the six-pointed star (and many other graphs) is R o o f : ( : t [1I C B:(2): Let C , = ( V , E, t ) = G,[ V , R ]
not a unit disk graph [90] (see Figs. 4 and 5). belong to G, [ 11 where R = { ( T ( i ) , d ( i ) ) l i = 0 , --- ,m}. For
Theorem 43: F*D-CAP(*; *) is equivalent to a subproblem each u in V , let D , be the unit disk centered at ur = u/d(O).
of GCP(*). Now uu is an element of E if and only if u # u and D ( u , u ) <
Proof: If V , P = { V 1 ; * . , V P } , R = { ( T j k ( i ) , d j k ( i ) ) l i = d ( 0 ) i f a n d o n l y i f u # u a n d D ( u r , u r ) < l i f a n d o n l y i f u # u
O;..,rn;j,k=l;..,p}andB={bl;..,bp}CQ+isan and D , and D , have nonempty intersection. Therefore, { D , I u
instance of F*D-CAP(*; *) and rb, 2 = 1, * * * ,p and C ( B ) are is in V } is an intersection model forG = ( V , E ) and G belongs
HALE: FREQUENCY 1511

to B1(2). By definition, t is an edge constraint generated by Proof: The proof is very similar to the proof of Theorem
R and therefore G, belongs to B:(2). B : ( 2 ) C G, [ 11 : Let 45.
G, = ( V , E , t ) belong to B f ( 2 ) . By definition G = ( V , E ) has The following results
are immediate corollaries. Q.E.D.
an intersection model (0, ; u is in V } and if u' is the center of Theorem 55:F*D-CFAP is equivalent to CP(*; *) restricted
D,, then V' = { u ' ( u is in V } is a subset of the plane. Also by to B(2).
definition of B : ( 2 ) , t is generated by R = { ( T ( i ) , d ( i ) ) l i =0 , Theorem56: F*D-FAP,F*D-FAPOL and F*D-FAPOare
* ,m } a set of F*D constraints and G , is an edge constrained equivalent,respectively, toGCP(*; *), GCPOL(*; *), and
-
graph generated by V' and R ' = { ( T ( i ) , d ' ( i ) ) l i= , * * , m } GCPO(*;*) restricted to B**(2).
-
where d ' ( i ) = d ( i ) / d ( O )for i = 0,* ,m . Q.E.D. Theorem 57: F*D-CCAP,F*D-CAP,F*D-CAPOL, F*D-
We have the following results as corollaries to Theorem 45. CAPO, F*D-CCAP(*), F*D-CAP(*), F*D-CAPOL(*; *),
Theorem 46: F*D-CCAP is equivalent t o CP restricted to F*D-CAPO(*), F*D-CCAP(*; *), F*D-CAP(*; *), F*D-
E1 (2). CAPOL(*; *), F*D-CAPO(*; *), F*D-CFAP, F*D-FAP,
Theorem 47: F*D-CAP is equivalent to GCP restricted to F*D-FAPOL, and F*D-FAPO are NP-hard.
Bf(2). Proof: In April of 1980, J. B. Orlin demonstratedthat
Theorem 48: F*D-CAPOL is equivalent to GCPOL restricted CP restricted to B 1 (2) is NP-hard. The result follows from the
to B: (2). fact that F*D-CCAP is a subproblem of each of the others.
Theorem 49: F*D-CAPO is equivalent to GCPO restricted Q.E.D.
to B: (2). C. Polynomial Time Subproblems
A graph G = ( V , E ) is called a disk graph if it has an inter- We now exploit the equivalence between frequency assign-
section model { D , I u is in V } consisting of closed disks in the ment problems and graph coloring to obtain efficient solutions
plane each of which has rational diameter <1 (e.&see Fig. 4). for some important real world problems. For instance, if the
Let B(2) denote the class of all disk graphs. If G = ( V , E ) transmitters and receivers that tune to them are restricted to
belongs to B(2) and (0, Iu is in V } is an intersection model lie on a straight line (as along a highway, a pipe line, etc.) then
for G, then let P = (41 the diameter of D , = q for some u in the subproblem of F*D-CCAP(*) corresponding to this situa-
V } C Q', let IPI = p, let 41,* * , q p be a list of P, let Vi = tion is equivalent to a subproblem of CP restricted to interval
(uI u is in V and the diameter of D , = qi} for i = 1, * * * ,p , let graphs and the algorithm [301 is an efficient solution for this
R = { ( T i k ( i ) , d i k ( k ) ) l i = O , . . . , m j; , k = l ; * * , p } be a set problem. Also, an obviousmodification of this algorithm
of F*D constraints for the -
mixed service { V I , * , V p } and yields an efficient solution for the analogous subproblem of
let E = { b l , * * , bp} C Q '
. Let d ; k ( i ) = dii(i)/dik(O) for F*D-CCAP(*;*).Indeed thetransmitters need not be omni-
i = 0, * * , m ; j , k = 1, . * ,p , let u' denote the center of D , directional and the highway need not be straight; itis sufficient
for each u in V , and let rb, k? = 1, * * , p be as in Section V-B. to require that the highway intersect the coverage area of each
Define t : E + P ( Z g ) by t(uu)={hr;2Ik?=l;..,p, h is in transmitter in a simple arc. More generally, if the locations of
T'k ( i ) where u is in Vi, u is in V k and i is the largest integer for transmitters are restricted in such a way that the resulting gen-
which D ( u ' , u ' ) < d i j ( k ) } . Now G , = ( V , E , t ) is an edge con- erated subclass of B(2) is made up of perfect graphs then L.
strained B(2) graph generated by R and B . Let E * ( 2 ) denote Lovasz has found, using L. G. Khachian's ellipsoid method, an
the class of all edge constrained B(2) graphs obtained in this efficient solution for this subproblem of F*D-CCAP(*) (soon
way, and let Bg(2) denote the subclass of E * ( 2 ) that results to be published).
-
when bi = b for i = 1, * * ,p . Note that E : (2) is the subclass If thetransmitters arerestricted to lie onthe circumfer-
that results when p = 1. ence of a circle (as in a ring network) then the subproblem of
Theorem 50: Eg(2) = G , [ *] and B*(2)= G, [*; *] F*D-CCAP corresponding to this situation is equivalent to a
Proof: The proof is very similar to the proof of Theorem subproblem of CP restricted to proper circular-arc graphs and
45. Q.E.D. the algorithm [49] is an efficient solution for this problem.
We have the following results as corollaries. More generally, if the transmitters are restricted to lie on the
Theorem 51: F*D-CCAP(*) and F*D-CCAP(*; *) areequiv- circumferences of concentric circles, then the corresponding
dent to CP restricted to B(2) and CP(*) restricted to E ( 2 ) , subproblem of F*D-CCAP(*)(where if u is an element of
respectively. ui, then u lies upon the circle centered at (0,0) with radius
Theorem 52: F*D-CAP(*), F*D-CAPOL(*), and F*D- 4 1 + ( d i / 2 ) * ) is equivalent to CP restricted to circular-arc
CAPO(*) areequivalent,respectively, to GCP, GCPOL, and graphs in which arcs are restricted t o be on the unit circle and
GCPO restricted to Eg(2). to have arc length no longer than pi. (To see this, if D i is a
Theorem 53: F*D-CAP(*; *), F*D-CAPOL(*; *), and disk with radius ri centered at polar coordinates (Ri,a i ) where
F*D-CAPO(*; *) areequivalent,respectively, toGCP(*), Ri = d m ,then let af be the circular arc with midpoint at
GCPOL( *), and GCPO( *) restricted to B* (2). (1, ai) and radian measure 2 arctan ri. Clearly, af and a; are
Let G = ( V , E ) belong to B(2), let { D , Iu is in V } ,P = { q l , disjoint iff Di and Di are disjoint.) Therefore, if the number of
* , q p ) , {VI, * * * , V p } , and B be as above. Let s = {sjk l j , channels (or colors) available is fixed at k I I VI (as is usually
k=l;..,p}, d={djklj, k=l;**,p}, and T = { T j k l j , the case in practical problems), then there is a polynomial time
k = 1, * * ,p} be as in Section V-C. Define t : E + P ( Z i ) and algorithm which produces a minimum span assignment using k
s:E+ 'Q by t ( u u ) = Tjk(djkD(u', u ' ) ) and ~ ' ( u u ) = s ; ~ ( d j kor fewer channels, if such an assignment exists [48].
D(u', u ' ) ) when u is in Vi, u is in V,, and j , k = 1, * , p . 0 . In Section 111, we remarked that potentially useful informa-
Now, G , = ( V , E , t , s f ) is a doubly edge constrained B ( 2 ) graph tion may be encoded when F*D constrainedproblemsare
generated by T , s, and d . Let E**(2) denote the class of all modeled as frequency Constrained problems, and we indicated
doubly edge constrained B(2) graphs obtained in this way. that the frequency constrained approach should only be used
Theorem 54: G , [ *; * ] = E**(2). for problemsinwhichdistance separation plays no role. In
 1512 PROCEEDINGS OF THE IEEE, VOL. 6 8 , NO. 12, DECEMBER 1980

support of this view, if the preceeding problem is modeled as a requirements. One can use our approach to determine which
frequency constrained problem, then the circular-arc nature of taboo(s) to modify for themaximum gain in spectrum efficiency
the problem may be encoded. Although there is a polynomial [92]. As another example, consider the FM-broadcast service.
time algorithm which decodes this information [ 91 ] this algo- One may use ourapproach to evaluate the effectiveness of
rithm, its proof, and its efficient implementation are all non- assigning frequencies to the differentclasses of FM transmitters
trivial. A quickreading of [ 91 ] shouldconvince the reader in an interwoven fashion or of allowing frequencies t o be as-
that one should model any problem in which distance separa- signed to unevenly spaced discretefrequencies, etc. Finally,
tion plays a role as an F*D constrained problem. one may use our approach to accurately determine the amount
of spectrum to allocate for aproposed new service (given a
VIII. CONCLUDING
REMARKS projected saturated environment).
What remains to be done? As indicated in our discussion of
In this paper, we have introducedthe minimum-order ap-
exploiting the graph coloring connection: We need t o devise
proach to frequency assignment and have developed a theory
good algorithms and/or heuristics for assignment problems.
which relates this potentially useful approach to the traditional The smallest last [58], largest first [ 5 1 ] and saturation degree
minimum span approach. We have modeled existing (e.g., co-
[471 graph coloring heuristics have been generalized t o handle
channel, adjacent channel, UHF-TV) and potential (e.g., mixed
minimum span assignment problems [ l o ] , [92] and the mini-
service withinterwoven spectrum sharing) real world assign-
mum residual difficulty heuristic has recently appeared [ 181,
mentproblems as both F*D constrained and frequency con- but very little else has been done.
strained optimization problems. We have demonstratedthat What about performanceguarantees [63]-[65] for these
the frequency constrained approach is more general than the heuristics restricted t o F*D constrained problems (i.e., to disk
frequency-distance approach and should be avoided if distance
graphs)? None of the exact graph coloring algorithms has been
separation is employed to mitigate interference. We have shown
applied to the cochannel assignment problem. How fast do
that a restricted class of graphs, called disc graphs, plays a cen-
these algorithms run when restricted t o disk (or t o unit disk)
tralrolein F*D constrainedproblems. We have introduced graphs? There is no graph coloring algorithmor heuristic which
two generalized chromatic numbers and have shown that each exploits the special structure of unit disk or disk graphs. There
of the frequency assignment problems studied in this paper is is no known intrinsic characterization of unit disk graphs (a
equivalent to a generalized graph coloring problem. Using these
reasonable forbidden subgraphcharacterizationseems out of
equivalences and recent results concerning the complexity of the question, as a large list of infinite families of forbidden
graph coloring, we have shown that each of the general assign- subgraphs continues t o grow). Such a characterization would
ment problems studied in this paper is NP-hard, but thatseveral be helpful in other applicationsinvolving unit disk graphs [ 93 1-
important subproblems have polynomial time solutions. We [ 981. What is the complexity of the clique problem [ 231 for
have noted that the theory relating the minimum span and the unit disk graphs? Exhaustivesearchalgorithms are the only
minimum order approaches, as developed fortheF*D con- known exact solutions to nontrivial (i.e., problems involving
strained problems, remains valid for the frequency constrained constraints other thancochannel) minimum spanand minimum-
and the generalized graph coloring problems. order assignment problems; and although minimum span algo-
What is the significance of all of this? First of all, there are rithms may be readily obtained from graph coloring algorithms,
the standard benefits of knowing the complexity classifications it is not obvious that trivial modifications of these or other
of problems. That is, employers may choose notto spend known algorithms will work for minimum order problems.
money for the development of polynomial time solutions for There is no known polynomial time heuristic for nontrivial
the assignment problems now known to be NP-hard. They may minimum order assignment problems. Except forwhat we have
instead invest in thedevelopment of polynomial time solutions presented in this paper, there is no chromatic graph theory for
for subproblems of NP-hard problems, nonpolynomialtime edge constrained graphs. For example, there are no nontrivial
solutions for the NP-hard problems, which are almost always upper or lower bounds onX,(G, T ) , X , ( G, T , Q), and X,( G, t )
fast for practical problems, and/or heuristics for the NP-hard either for edge constrained graphs restricted t o 8 * ( 2 ) or for
problems,whichalmost always perform well for practical the general case (oneexpectsmany of the results found in
problems,etc. In addition, there are several ways t o exploit 1691 -181 1 to have analogs here).
the close connection between frequency assignment and graph In a 1964 U.S. Government report (see [ 2 ] ) , theannual
coloring. The many existing solutions [ 261 -[ 371, [ 391 ,[ 401, economic value of the electromagnetic spectrum was estimated
[421, [451-[47] (heuristics [50]-[68]) for the graph coloring to be $17 billion. Every facet of personal,commercial, and
problem may beapplieddirectly (without modification) to governmental life in the developed world relies heavily upon
cochannel assignment problems.If it can be demonstrated successful use of the spectrum. It is widely acknowledged that
that one of these almost always runs sufficiently fast(produces successful communication contributes to world health, safety,
sufficiently good approximate solutions), then it may be mod- understanding, and peace. Clearly, it is important that we ad-
ified t o handle more general assignment problems. If none of dress the unsolved problems discussed above.
the existing solutions (heuristics) shows promise even for co-
channelproblems, then a solution (heuristic) which exploits
ACKNOWLEDGMENT
the special structure of disk graphs may be devised for the F*D
constrainedcochannel assignment problemand subsequently The author wishes to thank Douglass D. Crombie, John P.
extended to more general problems. Murray, and Leslie A. Berry of the Institute for Telecommuni-
More generally, using the approach of this paper, one may cation Sciences forsupporting, guiding, and reviewing this
evaluate various proposed conventions, policies, and procedures work. The author is grateful to Scott Cameron of the Electro-
which are t o govern a new or existing communications service. magnetic Compatibility Analysis Center, Annapolis, MD;
For example, suppose that improvements in UHF-TV receivers Michael R. Garey of Bell Laboratories, Murray Hill, NJ; James
allow for the relaxations of some of the distance separation B. Orlin of the Massachusetts Institute of Technology, Cam-
HALE: FREQUENCY ASSIGNMENT 1513

bridge, MA;and Allen C. Tucker of the State University of Sbornik, vol. 24/26, p. 163 (in Russian) (Amer. Math. SOC.Trans-
lation, No. 79, 1952.)
New York at Stoney Brook, for giving their advice and dis- [27] C. Berge, Theory of Graphs and its Applications. Paris, France:
cussing their work in advance of publication. The author also Dunod, 19 5 8.
wishes to thank other workers at the BoulderLaboratories [ 2 8 ] F. Harary, Graph Theory. Reading, Ma: Addiaon-Wesley, 1969.
[ 2 9 ] N. Christofides, “An algorithm for the chromatic number ofa
whoprovidedinvaluableassistance;namely,Renee B. Horo- graph,”Comput. J., vol. 14, no. 1, pp. 38-39, Feb. 1971.
witz,whodidtheeditorial review;Susan K. Langer and [ 301 F. Gavril, “Algorithms for minimum colouring, maximum clique,
minimum covering, by cliques and maximum independent set of
Elizabeth L. McCoy whodidthetyping;and Victoria R. a chordal graph,” SZAM J. Comput. vol. 1, no. 2, pp. 180-187,
Schneller and Jane L. Watterson who provided bibliographical 1972.
assistance. [ 311 S. Even and A. Pnueli, “Permutation graphs and transitive graphs,”
J. ACM,vol. 19, no. 3, pp. 400-410, July 1972.
[ 3 2 ] A. A. Borovikov and V. A. Gorbatov, “A criterion for coloring of
REFERENCES the vertices of a graph,” Eng. Cybernetics, vol. 10, no. 4 , pp.
[ 11 D. M. Jansky, Spectrum Management Techniques, Germantown, 683-686, 1972.
MD: Don White Consultants, 1977. [ 3 3 ] J. Randall-Brown, “Chromatic scheduling andthe chromatic
(21 JTAC, “Spectrum engineering-The key t o progress,” New York: number problems,” Management Sa’.vol. 19.4, Part I, pp. 456-
IEEE, 1968. 463, Dec. 1972.
[ 31 H. Eden, H.W. Fastert, and K. H. Kaltbeitzer, “More recent meth- [ 3 4 ] A.C. Tucker, “Perfect graphs and an application to optimizing
ods of television network planning andthe results obtained,” municipal services,”SZAM Rev., vol. 15, pp. 5 8 5 4 9 0 , 1973.
E.B.U. Rev., no. 60-A, pp. 54-59, Apr. 1960. (351 S. I. Roschke and A. L. Furtado, “An algorithm for obtaining the
141 H. W. Fastert, “The mathematical theory underlying the planning chromatic number and an optimal coloring of a graph,” Znf. Pro-
of transmitter networks,” E.B. U.Rev., no. 60-A, pp. 60-69, Apr. cess. L e n (The Netherlands), vol. 2, no. 2, pp. 34-38, June 1973.
1960. [ 361 D.G. Corneil and B. Graham, “An algorithm for determining the
[ 51 B. H. Metzger, “Spectrum management technique,” presented at chromatic number of a graph,” SIAM J. Comput., vol. 2, no. 4 ,
38th Nat. ORSA Meet. (Detroit, MI), Fall 1970. pp. 311-318, Dec. 1973.
[ 61 J. J. Pawelec, “An algorithm for assignment of optimum frequen- [ 3 7 ] C. C. Wang, “An algorithm for the chromatic number of agraph,”
cies t o homogeneous VHF radio networks,” Telecommun. J., vol. J. ACMvol. 21,110. 3, pp. 385-391, July 1974.
40, pp. 21-27, 1973. (381 A. Tucker, “Coloring a family of circular arcs,” SZAM J. Appl.
[ 71 J. Arthur Zoellner, “Frequency assignment games and strategies,” Math., vol. 29, pp. 493-502, 1975.
ZEEE Trans. on Electromagn.Compat., vol. EMC-15, pp. 191- [ 3 9 ] N. Christofides, Graph Theory: An Algorithmic Approach, New
196, Nov. 1973. York: Academic Press, pp. 58-78, 1975.
[ S ] C.E. Dadson, J. Durkin, and R.E. Martin, “Cbmputer prediction [ 4 0 ] E.L. Lawler, “A note on the complexity of the chromatic num-
of field strength in the planning of radio systems,” ZEEE Trans. ber problem,” Znf. Process. Left., (The Netherlands), no. 3, pp.
Veh. Technol., vol. VT-24, pp. 1-8, Feb. 1975. 66-67, Aug. 1976.
[ 9 ] R. A. Frazier, “Compatibility and the frequency selection prob- (41
- 1. M. C. Golumbic, “The complexity of comparability graph recog-
lem,” ZEEE Trans. Electromagn. Compat., vol. EMC-17, pp. 248- nition and coloring,” Computing (Austria), vol. 18, no. 3, pp.
254, Nov. 1975. 199-208, 1977.
[ 10 ] S. H. Cameron, “Sequential insertion: An algorithm for conserving [ 4 2 ] S. H. Cameron, “The solution of the graph-coloring problem as a
spectrum in the assignment of operating frequencies to operating set-covering problem,” B E E Trans. Electromagn. Compat., vol.
systems,” Annapolis, MD: ECAC, Sept. 1975, (ECAC-TN-75- ECM-19, no. 3, Pt. 2, pp. 320-322, Aug. 1977.
0023). [ 4 3 ] A. M. Walsh and W. A. Burkhard, “Efficient algorithms for (3, 1)
[ 11 ] T. Sakaki, K. Nakashima, and Y. Hattori, “Algorithms for finding graphs,”Znform. Sci., vol. 3, no. 1, pp. 1-10, 1977.
in the lump both bounds of the chromatic number of a graph,” [44] P. K. Srimani, B.P. Sinha, and A. K. Choudhury, “A new method
Comput. J., vol. 19, no. 4, pp. 329-332, Nov. 1976. t o find out the chromatic partition of a symmetric graph,”Znt. J.
[ 121 R. J. Pennotti and R.R. Boorstyn, “Channel assignments for cel- Syst. Sci.,vol. 9, no. 12, pp. 1425-1437, Dec. 1978.
lular mobile telecommunications systems,” in Proc. ZEEE Nat. (451 S. M. Korman, “The graph-colouring problem,” in Combinatorial
Telecommunications Conf. (Dallas, TX), pp. 16.5-1-16.5-5, Nov. Optimization, N. Christofides, A. Mingozzi, P. Toth, andC. Sandi,
1976. Eds. Chinchester, England: Wiley, pp. 211-235, 1979.
[ 131 J. A. Zoellner and C.L. Beall, “A breakthrough in spectrum con- [ 4 6 ] C. McDiarmid, “Determining the chromatic number of a graph,”
serving frequency assignment technology,” IEEE Trans. Electro- SZAMJ. Comput., vol. 8, no. 1, pp. 1-14, Feb. 1979.
magn. Compat.,vol. EMC-19, pp. 313-319, Aug. 1977. [ 4 7 ] D. Brelaz, “New methods t o color the vertices of a graph,” Com-
[ 141 C.L. Beall, and M. J. Dash, “An automated frequency assignment mun. ACM, vol. 22, no. 4, pp. 251-256, Apr. 1979.
system for air voice communication circuits in the frequency band [ 4 8 ] M. R. Garey, D. S. Johnson, G.L. Miller, and C.H. Papadimitriou,
from 225 MHz to 400 MHz,” in Proc. ZEEE Int. Symp. Electro- “The complexity of coloring circular arcs and chords,” SZAM J.
magnetic Compatibility (Seattle, WA), pp. 302-304, Aug. 1977. Discrete Algebraic Methods, to be published.
[ I S ] P.A. Major, “A parameter-sensitive frequency-assignment method [ 4 9 ] J. B. Orlin, M. Bonucelli, and D.P. Bovet, “An O(n’) algorithm
(PSFAM),” B E E Trans. Electromagn. Compat., vol. EMC-19, pp. for coloring proper circular arc graphs,” SIAM J. Discrete Alge-
330-332, Aug. 1977. braic Methods, to be published.
[ 1 6 ] M. J.Dash and S. R. Green, “Parameter sensitivity analysis: An [SO] J. E.L. Peck and M. R Williams, “Examination Scheduling, algo-
approach used in the investigation of frequency assignment prob- rithm 286,”Commun ACM, vol. 9, no. 6, pp. 433-434, 1966.
lems,” in Proc. Conf. Electromagnetic Compatibility (Guildford, [ 5 1 ] D. J. A. Welsh and M. B. Powell, “An upper bound for the chro-
England), pp. 55-64, Apr. 1978. matic number of a graph and its application to timetabling prob-
[ 1 7 ] F. Box, “A heuristic technique for assigning frequencies to mo- lems,” Computer J., vol. 10, pp. 85-86, 1967.
bile radionets,” ZEEE 7km.v. Veh.Technol. vol. VT-27, pp. [ 521 I. Tomescu, “An algorithm for determining the chromatic number
57-74, May 1978. of a finite graph,” Econ. Comput. Cybern. Stud. Res.(Rumania),
[ 181 S. Cameron, and Y. Wu, “A frequency assignment algorithm based no. 1, pp. 69-81, 1969.
on a minimum residual difficulty heuristic,” in Proc. ZEEE Int. [ 531 D. C. Wood, “A technique for colouringagraphapplicable tolarge
Symp. EMC ’79(CH 13839 EMC), pp. 350-354, Oct. 1979. scale timetablingproblems,” Comput. J., vol. 12, pp. 317-319,
[ 191 S. A. Cook,“Thecomplexityoftheorem-provingprocedures,” 1968.
Proc. 3rdACMSymp. TheoryofComputing, pp. 151-158, 1971. [ 5 4 ] M. R. Williams, “The colouring of very large graphs,” in Combi-
[ 2 0 ] R. M. Karp, “Reducibilityamongcombinatorialproblems,” in natorial Structures and Their Applications, R.K. Guy, H. Hanani,
Complexity of Computer Computations, R.E. Miller and J. W. N. Sauer, and J. Schonheim, Eds. New York: Gordon and Breach,
Thatcher, Eds.New York: Plenum Press, pp. 85-104, 1972. 1970, pp. 477-478.
121 ] M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified [ 5 5 ] R. S. Wilkov and W. H. Kim, “A practical approach to the chro-
NP-complete problems,” in Proc. 6th ACM Annu. Symp. Theory matic partition problem,” J. Franklin Znst., vol. 289, no. 5, pp.
and Computing, pp. 237-267, 1974. 333-349, May 1970.
[ 221 M. R. Garey and D. S. Johnson,“The complexity of near-optimal [ 561 R. A. Draper, “A graph coloring algorithm and a scheduling prob-
graph coloring,”L ACM, vol. 23, no. 1, pp. 43-49, Jan. 1976. lem,” M.S. thesis, Naval PostgraduateSchoolMonterey, CA,
[ 2 3 ] -, Computers and Intractability: A Guide to the Theory of NP- 1971.
Completeness. San Francisco, CA: Freeman, 1979. [ 5 7 ] A. A. Kalnin’sh “Thecoloringof graphs in a linear numberof
[ 2 4 ] H. R. Lewis and C. H. Papadimitriou, “The efficiency of algo- steps,”Cybern., vol.. 7, no. 4, pp. 691-700, July-Aug. 1971.
rithms,”Scientific Amer.,pp. 96-109, Jan. 1978. [SS] D. W. Matula, W. G. Marble and J. D. Isaacson, “Graph coloring
[ 2 5 ] R. L. Brooks, “On colouring the nodes of a network,” in Proc. algorithms,” in Graph Theory and Computing, R.C. Read, Ed.
CambridgePhilosophy Society, vol. 37, pp. 194-197,1941. New York: Academic Press, 1972, pp. 109-122.
[ 2 6 ] A. A. Zykov, “On someproperties of linearcomplexes,” Mat. [ 59 1 D.W. Matula, “Bounded color functions on graphs,” Networks,
 1514 PROCEEDINGS O F THE IEEE, VOL. 68, NO. 12, DECEMBER 1980

v01. 2, pp. 29-44, 1972. creteMath. (The Netherlands), vol. 24, no. 1, pp. 1-6, Oct. 1978.
[ 6 0 ] M. R williams, “Heuristic procedures (if they work leave them [79] E. Nordhaus, E. and J. Gaddum, “On complementary graphs col-
alone),” Software Practice and Experience, vol. 4, no. 3, pp. 237- oring,” Amer. Math. Monthly, vol. 63, pp. 175-177, 1956.
240, July-Sept. 1974. [SO] J. A. Bondy, “Bounds for the chromatic number of a graph,” J.
[ a l l F. Dunstan, “Greedy algorithms for optimization problems,” pre- Combin. Theory, vol. 7, pp. 96-98, 1969.
sented at Euro I meeting, (Brussels, Belgium) Jan. 1975. [ 811 B. R. Myers, and R Liu, “A lower bound on the chromatic num-
[ 6 2 ] A. Tehrani, “Un algorithme de coloration,” Cahiers ducentre ber of a graph,”Nehoorks, vol. 1 , no. 3, pp. 273-271, 1972.
d’Ehtdes de Recherche Operationnelle,vol. 17, no. 2-4, pp. 395- [ 8 2 ] L.C. Middlekamp, “UHFtaboos-History and development,”
398, 1975. ZEEE Tmns. ConsumerElectron., vol. CE-24, pp. 514-519, Nov.
[ 631 D. S. Johnson, ‘Worst case behavior of Daph coloring algorithms,” 1978.
in h o c . 5 t h Southeastern ConE Combi&tories, Graph T h e o j K. Baker, Introduction to Sequencing and Scheduling, New York:
Computing pp. 513-528, 1974. ( W i e p e g , Canada: Utilitas Math- Wiley, 1974.
ematics Publishing.) E.G. Coffman, Jr., Computer and Job Shop Scheduling Theory,
D. S . Johnson,“Approximationalgorithms for combinatorial New York: Wiley, 1976.
problems,” J. Comput. Syst. Sci.,vol. 9, no. 3, pp. 256-278,1974. R. W. Conway, W. L. Maxwell, and L.W. Miller, Theory ofsched-
R. Karp and D. W. Matula, “Probabilistic behaviour of a naive uling. Reading, MA: Addison-Wesley, 1967.
coloring algorithmon random graphs,” Bull. Oper. Res. Soc. Amer., S. Elmaghraby Ed., Symposium on theTheory o f Scheduling.
vol. 23, suppl. 2, p. 264, Fall 1975. Berlin, Germany: Springer-Verlag, 1973.
‘ I J. Mitchem, “On various algorithms for estimating the chromatic J.L. Lenstra, Sequencing of Enumerative Methods. Amsterdam,
number of a graph,” Comput. J., vol. 19, no. 2, pp. 182-183, The Netherlands: Mathematisch Centrum, 1976.
May 1976. A. H. G. Rinnooy Kan, Machine Scheduling Problems: Classifia-
1 M. Kubale, and J. Dabrowski, “Empirical comparison of efficiency tion,Complexity and Computations. The Hague, The Nether-
of some graph colouring algorithms,” Arch. Autom. Telemech. lands: Nijhoff, 1976.
(Poland), vol. 23, no. 1-2, pp. 129-139, 1978. ‘ I W. K. Hale, “Optimalchannel assignment andchromatic graph
1 N. K. Mehta, “Performance of selected graph coloring algorithms- theory,” presented at MAAIAMSIASL Nat. Meet., Boulder, CO,
empirical results,”presented atthe 1980 TIMSIORSA Conf. Mar. 1980.
(Washington, DC), May 4-7, 1980. ‘ 1 A. M. Odlyzko and N. J. A. Sloane, “New bounds on the number
1 A.P. Ershov and G. I. Kozhukhin, “Estimates of the chromatic of unit spheres that can touch a unit spere in n dimensions,” I.
number of connected graphs,” Dokl. Akad. Nauk, vol. 142, pp. Combin. TheorySer. B (USA), vol. 26,110.3, pp. 276-294, Mar.
270-273; and Tmns. SovietMath., vol. 3, pp. 50-53, 1962. 1979.
-.. ..

1 H. S . Wilf, “The eigenvalues of a graph and itschromatic number,” 1 A. Tucker, “An effkient test for circular-arc graphs,” SIAM J.
J. London Math. SOC.,vol. 42, PP. 330-332. 1967. Comput.,vol. 9 , PP. 1-24, Feb. 1980.
[ 71 1 G. Szekeres and H. -S. Wilf,. “kn inequality for the chromatic [ 92 1 W. K. Hale, “Spictrum efficiency as a function of frequency dis-
number of a graph,” J. Comb. Theory, vol. 4, pp. 1-3, 1968. tance rules,” presented at ORSA/TIMS Nat. Meet. (Colorado
[ 7 2 ] J. H. Folkman, “An upper bound on the chromatic number of a Springs, CO), Nov. 10-12,1980.
graph,” Rand Corp., California, Rep. RM-5808-PR, NTIS no. [ 9 3 ] P. Armitage, “An overlap problem arising in particle counting,”
AD-684 527, Febr. 1969. Biometn’ka,vol. 36, pp. 257-266, 1949.
[ 7 3 ] P. Holgate, “Majorants of the chromatic number ofarandom (941 C. Mack, “The expected number of clumps when convex laminae
graph,” J. Roy. Statistics SOC. Ser.B, vol. 31, pp. 303-309, 1969. are placed at random and with random orientation on a plane
[ 74 1 A. J. Hoffman, “On eigenvalues and colorings of graphs,”in Graph area,” in Proc. Cambridge Philosophy Society, vol. 50, pp. 581-
Theory and Its Applications, B. Harris, Ed. New York: Academic 585,1954.
R M ,pp. 79-91, 1970. [ 95 1 E. Gilbert, “Random plane networks,” J. SOC.Zndust. Appl. Math,
[ 75 ] B. Andrasfai, P. Erdos, and V. T. Sa,“On the connection between vol. 9 , no. 4 , pp. 533-543, Dec. 1961.
chromatic number, maximal clique and minimal degree of a graph,” [ 9 6 ] -, “The probability of covering a sphere with N circular caps,”
Discrete Math. (TheNetherlands), vol. 8, no. 3, pp. 205-218, Biometrika,vol. 52, nos. 3 and 4 , pp. 323-330, 1965.
May 1974. [ 97 I H. DeWitt and M. Krieger, “An efficient algorithm for computing
[ 7 6 ] J. Lawrence, “Covering the vertex set of a graph with subgraphs the minimal spanning tree of a graph in a Euclidean-like space,”
of smaller degree,” DiscreteMath. (The Netherlands), vol. 21, in Proc. 8th Hawaii Znt.ConE SystemSciences, pp. 253-255,
no. 1, pp. 61-68, Jan. 1978. 1975.
[771 P. k Catlin, “A bound on the chromaticnumber of a graph,’’ [ 9 8 ) -, “Expected structure of Euclidean graphs,” presented at the
Discrete Math. (The Netherlands), vol. 22, no. 1, pp. 81-83, Apr. 1976 Symp. New Directions and Resent Results in Algorithms
1977. and Complexity, Carnegie-Mellon Univ., Pittsburgh, PA, Apr.
[78 1 -, “Another bound on the chromatic number of a graph,” Dis- 7-9,1976.