Premium
Optimal I ‐Intersection assignments for graphs: A linear programming approach
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.3230130301
Subject(s) - intersection (aeronautics) , linear programming , interval graph , vertex (graph theory) , scheduling (production processes) , combinatorics , integer programming , mathematics , computer science , graph , mathematical optimization , algorithm , pathwidth , line graph , engineering , aerospace engineering
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.