Optimal I-Intersection assignments for graphs: A linear programming approach

✍ Scribed by Robert J. Opsut; Fred S. Roberts

• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 409 KB
• Volume: 13
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230130301

✦ Synopsis

An intersection assignment for a graph is the assignment of a set t o 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.

[ 15 I K. E. Stoffers, Scheduling of traffic lights-A new approach. Transportation Res. 2 (1968) 199-234.