Thumbnail
Access Restriction
Subscribed

Author Oakford, R. V. ♦ Salazar, A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Graph ♦ Nondirected network ♦ Strongly connected subgraph ♦ Subgraph ♦ Scheduling ♦ Examination scheduling ♦ School scheduling
Abstract The problem classically titled “The Examination Schedule Problem” takes various forms in the literature. Most of these formulations can be presented in the terminology of classical Network Theory. One such formulation is: Given a nondirected network, partition its nodes into a minimal number of subsets such that no two members of the same subset are connected by an arc.An obvious lower limit to this number is the size of the largest strongly connected subgraph. Kirchgassner proved that an upper limit is this size plus one.One logical extension of the previous work is the introduction of variable length examinations where W(I) is the number of periods for exam I. The object of this paper is to generalize the definition of largest strongly connected subgraph to include the weighting of nodes, to present an approximate algorithm which usually finds the largest strongly connected subgraph, and to discuss the application of this algorithm to the solution of school scheduling and exam scheduling problems.
Description Affiliation: Stanford Univ., Stanford, CA (Salazar, A.; Oakford, R. V.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 17
Issue Number 12
Page Count 3
Starting Page 696
Ending Page 698


Open content in new tab

   Open content in new tab
Source: ACM Digital Library