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

Robert J. Opsut; Fred S. Roberts

doi:10.1002/net.3230130301

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

Robert J. Opsut, Fred S. Roberts

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

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)
Pages (from-to)	317-326
Number of pages	10
Journal	Networks
Volume	13
Issue number	3
DOIs	https://doi.org/10.1002/net.3230130301
State	Published - 1983

All Science Journal Classification (ASJC) codes

Software
Information Systems
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1002/net.3230130301

Cite this

@article{e2bf0fd511d641298d3e8c646dc85608,

title = "Optimal I‐Intersection assignments for graphs: A linear programming approach",

abstract = "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.",

author = "Opsut, {Robert J.} and Roberts, {Fred S.}",

year = "1983",

doi = "10.1002/net.3230130301",

language = "English (US)",

volume = "13",

pages = "317--326",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Optimal I‐Intersection assignments for graphs

T2 - A linear programming approach

AU - Opsut, Robert J.

AU - Roberts, Fred S.

PY - 1983

Y1 - 1983

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0020824702&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020824702&partnerID=8YFLogxK

U2 - 10.1002/net.3230130301

DO - 10.1002/net.3230130301

M3 - Article

AN - SCOPUS:0020824702

SN - 0028-3045

VL - 13

SP - 317

EP - 326

JO - Networks

JF - Networks

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this