Premium
ON THE MOBILE RADIO FREQUENCY ASSIGNMENT PROBLEM AND THE TRAFFIC LIGHT PHASING PROBLEM
Author(s) -
Roberts Fred S.
Publication year - 1979
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.1979.tb32824.x
Subject(s) - frequency assignment , combinatorics , phaser , vertex (graph theory) , disjoint sets , mathematics , graph , set (abstract data type) , intersection (aeronautics) , discrete mathematics , fibonacci number , chromatic scale , computer science , physics , telecommunications , engineering , optics , programming language , aerospace engineering
S ummary The problem of assigning frequencies to mobile radio telephones and the problem of assigning green light times to traffic streams at an intersection both deal with the assignment of a set S(x) to each vertex x of a graph G. The frequency assignment problem is concerned with set colorings: S(x) and S(y) are disjoint if x and y are joined by an edge. The traffic light phasing problem is concerned with set phasings: S(x) and S(y) are disjoint if x and y are not joined by an edge. This paper obtains some results on the existence and minimum size of set colorings and phasings under special restrictions on the sets S(x) , for example, that each S(x) is a real interval or a set of n integers, or a set with at least a certain number of elements. Some of these results extend recent work on the n ‐tuple chromatic number. Finally, the set phasing and coloring problems are related to the problem of assigning sets S(x) to vertices of a graph so that S(x) and S(y) overlap if and only if x and y are joined by an edge. Results about existence and minimum size of such set assignments are given.