Graphs are discrete structures composed of vertices and edges
connecting these vertices. Graphs are used in almost all disciplines as
abstract models for the representation and study of a wide range of relations
and processes in physical, biological, social and information systems. Many
practical problems in a variety of areas like computer and communication
networks, social networks, transportation networks, cellular networks,
linguistics, chemistry, physics, biology can be represented and studied by graphs.
Realworld entities  like molecules, persons, groups, roles,
species, computing and communication devices, terms  correspond to vertices.
Relations among such entities  like preference, domination, independence,
interference, proximity, constraints  imply the existence of edges between
corresponding vertices. Thus, focusing on the abstract graph model instead of
studying each particular instance as a different realworld problem reveals
common underlying properties, deficiencies and principles. In this way,
efficient approaches to realworld problems emerge from the theoretical study
of their abstractions.
In this work, we use graph coloring to propose efficient solutions
to scheduling problems arising in higher education. The objective of the graph
coloring problem is to assign colors to graph vertices so that adjacent
vertices, i.e., vertices connected by an edge, receive different colors. We
consider as the objective of scheduling problems in higher education, like
lecture and exam scheduling, to assign time/day slots to teaching or
examination activities so that the maximum number of students can attend them
with the fewest possible conflicts.
Our main motivation has been the crucial issue of efficient course
and exam schedules often arising in departments of the University of Patras,
Greece. Students usually have to attend lectures or exams scheduled in
overlapping or simultaneous time slots. However, course and exam schedules are
created based on heuristic approaches which may work well on average but
certainly leave several room for improvement.
What if a graphtheoretic approach were used? Courses correspond to
vertices of a graph and there is an edge between two vertices if and only if an
appropriately selected minimum population of students attends corresponding
courses (lectures/exams). Then, a coloring of such an underlying graph suggests
an appropriate schedule for teaching/examination activities.
Using a simple coloring algorithm and the MATLAB programming
environment, we have designed and developed a scheduling application which
receives as input courses and constraints and outputs an efficient
lecture/examination schedule. Experimental evaluation suggests that our
application works well in practice. Ongoing work focuses on the use of a more
involved coloring algorithm for addressing more complex course scheduling
instances while minimizing required time resources.
Konular  Sosyal 

Dergi Bölümü  Makaleler 
Yazarlar 

Bibtex  @araştırma makalesi { ijaedu309802,
journal = {International EJournal of Advances in Education},
issn = {},
eissn = {24111821},
address = {OCERINT International Organization Center of Academic Research},
year = {2017},
volume = {3},
pages = {51  59},
doi = {10.18768/ijaedu.309802},
title = {EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING},
key = {cite},
author = {Athanassopoulos, Stavros and Papaioannou, Evi and Kaklamanis, Christos}
} 
APA  Papaioannou, E , Athanassopoulos, S , Kaklamanis, C . (2017). EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING. International EJournal of Advances in Education, 3 (7), 5159. DOI: 10.18768/ijaedu.309802 
MLA  Papaioannou, E , Athanassopoulos, S , Kaklamanis, C . "EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING". International EJournal of Advances in Education 3 (2017): 5159 <http://ijaedu.ocerintjournals.org/issue/28950/309802> 
Chicago  Papaioannou, E , Athanassopoulos, S , Kaklamanis, C . "EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING". International EJournal of Advances in Education 3 (2017): 5159 
RIS  TY  JOUR T1  EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING AU  Evi Papaioannou , Stavros Athanassopoulos , Christos Kaklamanis Y1  2017 PY  2017 N1  doi: 10.18768/ijaedu.309802 DO  10.18768/ijaedu.309802 T2  International EJournal of Advances in Education JF  Journal JO  JOR SP  51 EP  59 VL  3 IS  7 SN  24111821 M3  doi: 10.18768/ijaedu.309802 UR  http://dx.doi.org/10.18768/ijaedu.309802 Y2  2017 ER  
EndNote  %0 International EJournal of Advances in Education EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING %A Evi Papaioannou , Stavros Athanassopoulos , Christos Kaklamanis %T EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING %D 2017 %J International EJournal of Advances in Education %P 24111821 %V 3 %N 7 %R doi: 10.18768/ijaedu.309802 %U 10.18768/ijaedu.309802 
ISNAD  Papaioannou, Evi , Athanassopoulos, Stavros , Kaklamanis, Christos . "EFFICIENT COURSE AND EXAM SCHEDULING USING GRAPH COLORING". International EJournal of Advances in Education 3 / 7 (Nisan 2017): 5159. http://dx.doi.org/10.18768/ijaedu.309802 