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

Robert J. Opsut, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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 languageEnglish (US)
Pages (from-to)317-326
Number of pages10
Issue number3
StatePublished - 1983

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Optimal I‐Intersection assignments for graphs: A linear programming approach'. Together they form a unique fingerprint.

Cite this