A graph coloring algorithm for large scale scheduling problems

Vahid Lotfi; Sanjiv Sarin

doi:10.1016/0305-0548(86)90061-4

A graph coloring algorithm for large scale scheduling problems

Vahid Lotfi, Sanjiv Sarin

Industrial and Systems Engineering

State University of New York

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

Abstract

Graph coloring finds application in a variety of conflict resolution problems, such as examination scheduling. Since it is an NP-complete problem, a number of heuristic methods have been suggested for its solution. We present a new heuristic solution procedure designed to produce good suboptimal solutions with very little computational effort.

Original language	English
Pages (from-to)	27-32
Number of pages	6
Journal	Computers and Operations Research
Volume	13
Issue number	1
DOIs	https://doi.org/10.1016/0305-0548(86)90061-4
State	Published - 1986

Access to Document

10.1016/0305-0548(86)90061-4

Cite this

@article{525554d65c6046cb82d0e4b8a868a12e,

title = "A graph coloring algorithm for large scale scheduling problems",

abstract = "Graph coloring finds application in a variety of conflict resolution problems, such as examination scheduling. Since it is an NP-complete problem, a number of heuristic methods have been suggested for its solution. We present a new heuristic solution procedure designed to produce good suboptimal solutions with very little computational effort.",

author = "Vahid Lotfi and Sanjiv Sarin",

year = "1986",

doi = "10.1016/0305-0548(86)90061-4",

language = "English",

volume = "13",

pages = "27--32",

journal = "Computers and Operations Research",

issn = "0305-0548",

number = "1",

}

TY - JOUR

T1 - A graph coloring algorithm for large scale scheduling problems

AU - Lotfi, Vahid

AU - Sarin, Sanjiv

PY - 1986

Y1 - 1986

N2 - Graph coloring finds application in a variety of conflict resolution problems, such as examination scheduling. Since it is an NP-complete problem, a number of heuristic methods have been suggested for its solution. We present a new heuristic solution procedure designed to produce good suboptimal solutions with very little computational effort.

AB - Graph coloring finds application in a variety of conflict resolution problems, such as examination scheduling. Since it is an NP-complete problem, a number of heuristic methods have been suggested for its solution. We present a new heuristic solution procedure designed to produce good suboptimal solutions with very little computational effort.

UR - https://www.scopus.com/pages/publications/0022582293

U2 - 10.1016/0305-0548(86)90061-4

DO - 10.1016/0305-0548(86)90061-4

M3 - Article

SN - 0305-0548

VL - 13

SP - 27

EP - 32

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 1

ER -

A graph coloring algorithm for large scale scheduling problems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this