An intersection assignment for a graph is the assignment of a set to each vertex so that edges correspond to pairs of sets which overlap. Intersection assignments are studied in which each set is a real interval, perhaps of specified minimum length. In particular, linear programming methods are used to see how to minimize the measure of the union of intervals in such an assignment, and how to maximize the sum of the lengths of the intervals in such an assignment. The results have application to a variety of scheduling problems.
|Original language||English (US)|
|Number of pages||10|
|State||Published - 1983|
All Science Journal Classification (ASJC) codes
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications