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

State University of New York

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

38 Scopus citations

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. © 1986.

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 - Jan 1 1986

Access to Document

10.1016/0305-0548(86)90061-4

Cite this

@article{05fe5be9b7c14ceba1265af629b2e296,

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. {\textcopyright} 1986.",

author = "Vahid Lotfi and Sanjiv Sarin",

year = "1986",

month = jan,

day = "1",

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/1/1

Y1 - 1986/1/1

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. © 1986.

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. © 1986.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0022582293&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=0022582293&origin=inward

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