Premium
I ‐Colorings, I ‐Phasings, and I ‐Intersection assignments for graphs, and their applications
Author(s) -
Opsut Robert J.,
Roberts Fred S.
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130302
Subject(s) - disjoint sets , combinatorics , intersection (aeronautics) , vertex (graph theory) , set (abstract data type) , frequency assignment , independent set , graph coloring , interval graph , computer science , mathematics , graph , discrete mathematics , phaser , pathwidth , line graph , telecommunications , physics , optics , engineering , programming language , aerospace engineering
This paper studies set assignments on graphs, functions assigning a set S ( x ) to each vertex x of a graph, and specifically set assignments where each set is a real interval, perhaps of specified minimum length. Such set assignments arise in applied problems dealing with fleet maintenance, mobile radio frequency assignment, task assignment, traffic phasing, banquet preparation, and computer storage optimization. These problems are briefly discussed. They are translated into problems of finding a set coloring [a set assignment in which an edge between x and y implies that S(x ) and S(y ) are disjoint], a set phasing [a set coloring of the complementary graph], or a set intersection assignment. The paper presents methods for finding set colorings, phasings, and intersection assignments in which the measure of the union of the intervals S(x ) is minimized or in which the sum of the lengths of the S(x ) is maximized.