University Course Timetabling Using ACO: A Case Study on Laboratory Exercises - [PDF Document] (2024)

University Course Timetabling Using ACO: ACase Study on Laboratory Exercises

Vatroslav Dino Matijas, Goran Molnar, Marko Cupic, Domagoj Jakobovic, andBojana Dalbelo Basic

Faculty of Electrical Engineering and Computing,Unska 3, 10000 Zagreb, Croatia

University of [emailprotected], {goran.molnar2|marko.cupic|

domagoj.jakobovic|bojana.dalbelo-basic}@fer.hr

Abstract. The ant colony optimisation metaheuristic has shown promiseon simplified artificial instances of university course timetabling prob-lems. However, limited work has been done applying it to practicaltimetabling problems. In this paper, we describe the application of theant colony optimisation to a highly constrained real–world instance ofthe university course timetabling problem. We present the design of thememory–efficient construction graph and a sophisticated solution con-struction procedure. The system devised here has been successfully usedfor timetabling at the authors’ institution.

1 Introduction

Almost every type of human organisations is occasionally faced with some formof timetabling tasks. The University Course Timetabling Problem (UCTP) andits variations are parts of the larger class of timetabling and scheduling prob-lems. A large number of university timetabling problems have been described inthe literature, and they differ from each other based on the type of institutioninvolved, the entities being scheduled and the constraints in the definition of theproblem.

Due to inherent complexity and variability of the problem, most real–worldtimetabling problems are NP–complete [1]. This calls for use of heuristic algo-rithms which do not guarantee an optimal solution but can usually generatesolutions that are good enough for practical use. Due to their manageabilityand good performance (if properly implemented), metaheuristic techniques haveshown to be particularly suitable for solving these kinds of problems.

In this work1, we focus on the Laboratory Exercises Timetabling Problem(LETP), framed as an example of the university course timetabling problem.The work described is a part of the research on two different metaheuristics for

1 This work has been supported by the Ministry of Science, Education and Sports,Republic of Croatia and under the grants No 036-1300646-1986 and ..........

timetable construction: genetic algorithm [2] and ant colony optimisation meta-heuristic. Constructing a system for solving instances of LETP is challengingboth technically and administratively. Along with the efficient timetable pro-duction system, a feature–rich model of the timetable constraints is devised. Itis necessary for the system to be able to account for a complex set of constraintsbecause various departments at our institution have very different ideas aboutwhat a good timetable should look like. The definition of LETP is devised in closecoordination with the departments and is constantly evolving. Therefore, a goodmodular design that supports changes in the problem definition is necessary.

Our approach is based on the Ant Colony Optimisation metaheuristic (ACO),proposed by Dorigo et al. [3]. It is a distributed stochastic probabilistic construc-tive search procedure, inspired by the foraging behaviour of ants. It utilises aproblem representation in the form of a construction graph, on which suggestedsolutions are constructed by artificial ants. ACO has already shown promise forvarious timetabling applications. It has been successfully applied to various arti-ficially generated UCTP datasets in [4, 5] and in [6] its performance is comparedwith that of several other metaheuristics. ACO has also been applied to artifi-cially generated instances of the examination timetabling problem, for examplein [7]. However, as noted in [8],

“A major identified weakness in the current approach to OperationalResearch is described as follows: a gap still remains between the output ofa successful research project and what is needed for direct use by industry.In general, the area of educational timetabling is one such area.”

Solving real such problems is a difficult task that involves modelling and handlingvarious kinds of constraints which are usually simplified in academic problems.Moreover, only a few, relatively basic UCTP representations have been proposedin literature for use with ACO. It has been shown that these representations donot satisfy the requirements imposed by complex, large LETP instances.

This work is an effort to bridge this gap between the theory and practiceof automated timetabling and to build an ACO–based system that satisfies thetimetabling needs of our institution. The result of our work is an ACO–basedtimetabling system suitable for practical use.

The remainder of this paper is organised as follows: Section 2 introduces theactual timetabling problem, and in Section 3 we elaborate our approach. Section4 presents the results, and Section 5 concludes the paper.

2 University Course Timetabling Problem

2.1 Problem Statement

The timetable construction problem is a combinatorial optimisation problemthat consists of four finite sets: (i) a set of meetings, (ii) a set of availableresources (e.g. rooms, staff, students), (iii) a set of available time–slots, and (iv)a set of constraints. The problem is to assign resources and time slots to each

given meeting, while maintaining constraints satisfied to the highest possibleextent. The University Course Timetabling Problem (UCTP) is a timetablingproblem where the given data consists of a set of students and sets of courses thateach of the students needs to attend. A course is a set of events that need to takeplace in the timetable. The main characteristic that distinguishes the universitycourse timetabling problem from other types of timetabling problems is the factthat students are generally allowed to choose the courses in which they wishto enrol [9]. A set of constraints is usually divided into hard constraints whoseviolation makes the timetable suggestion infeasible, and soft constraints, rulesthat improve the quality of timetables, but are allowed to be violated.

The above description of the UCTP defines a broad range of problems, whosecomplexity significantly depends on the specific constraints defined. Particulartimetabling applications are usually focused on a more strictly defined subsetof the problems, as the constraints and dimensions of the problem vary amonginstitutions. We use the same approach, giving a detailed formal description ofthe problems for which our application is designed.

2.2 Definition of Laboratory Exercise Timetabling Problem

The laboratory exercise timetabling problem is defined as a six–tuple:

LETP = (T, L,R,E, S,C) ,

where T is a set of time–quanta in which the scheduling is possible, L is a set oflimited assets present at the university, R is a set of rooms, E is a set of eventsthat need to be scheduled, S is a set of attending students, and C is a set ofconstraints. We assume that the durations of all the events can be quantified asmultiples of a fixed value of time that we call a time–quantum. A time–slot isdefined as one or more consecutive time–quanta in the timetable. The durationof the quantum reflects a trade–off between the precision of scheduling and thesize of the search space.

The set of limited assets (resources) shared among the different exercises isdenoted L. For each resource l ∈ L, a fixed number of workplaces can use theresource concurrently.

Each room is defined as a set of workplaces, atomic room resources varyingfrom room to room, such as seats in ordinary classrooms, computers in computerclassrooms, etc. For each room r ∈ R, the number of workplaces, denoted sizer ∈N is defined. For each of the events, the desired number of students per workplaceis defined. Since some rooms may not be available all the time, a set of timequanta Tr ⊆ T in which the room is available is defined for each room.

Events have the following set of properties:

– Each event e has a duration, denoted dure ∈ N, a multiple of a time quantum.– Each event e has an acceptable room set Re ⊆ R.– Each event e has a suitable time quanta set, denoted Te ⊆ T .– The set of limited assets used by the event is denoted Le ⊆ L.

– The number of staff available for each event and the number of staff neededfor event e when held in the room r are given. Because each of the de-partments at our institution produces staff timetables independently of oursystem, staff is not defined as a separate entity of the LETP.

– An ordering relation, denoted �d can be defined for a pair of events. Therelation e2 �d e1 is true if and only if e2 needs to be scheduled at least ddays after e1.

– The maximum number of rooms to be used concurrently for the event e canbe defined.

– An event timespan can be defined to ensure that all of the time–quanta inwhich the event is scheduled are within a specified time interval.

– For each event e, the number of students per workplace is denoted spwe ∈ N.

The set S is the set of students that are to be scheduled. Each student s ∈ Shas the following set of properties: (i) a set of time quanta Ts ⊆ T when eachstudent s is free, and (ii) a non–empty set of events he or she needs to attend,denoted Es ⊆ E.

The requirements of the courses are represented by a set of constraints C.The constraints are divided into hard constraints Ch, which are essential for thecourses, and soft constraints Cs, which may require some manual intervention ifthey are not met. Hard constraints Ch are defined as follows:

– All of the properties of limited assets, rooms, events and students need tobe satisfied in the timetable.

– Each room can only be occupied by one event at a time.– Students can attend only one event at a time.– Each event e occupies dure consecutive quanta of the room.– At most sizer · spwe students can be placed in room r used for the event e.– Enough teaching staff must be available to attend each event.

The set of soft constraints Cs contains one element: the students must attendall the events they are enrolled in. Defining this constraint as soft may seemirrational, but the reasoning behind this is as follows: ’hard’ constraints aresimply those that are satisfied at all times in any solution suggestion in ourimplementation, whereas for the ’soft’ constraints this may not be the case. ’Soft’constraints are defined as such because it was not known in advance whetherthere even exists a solution that satisfies all the constraints (given the complexrequirements). In other words, our approach tries to find the best solution withinthe imposed constraints and possibly to give a feedback to the course organisersif some are still severely violated. In the remainder of the text, the term ’feasiblesolution’ denotes a solution that satisfies at least the hard constraints as definedabove.

3 Solving LETP Using Ant Colony Optimisation

3.1 Construction Graph

The main issue in applying ACO to a problem is to find an appropriate rep-resentation that can be used by the artificial ants to build solutions [3]. This

representation is called the construction graph. To ensure that the problem rep-resentation is suitable for large instances of LETP, memory–efficiency is themain design goal. The construction graph we devised can be seen in figure 1.Semantically, each of the nodes represents one of the following: a student, anevent or a dock node. A dock is an ordered pair of the room and beginning timein which an event can be scheduled, e.g., (ComputerLab-2, (2010-09-08, 10:00)).

An edge connecting a dock node and an event node means that the eventcan be scheduled in that time and place. This means that the dock representsthe room and time that are suitable for that event. Dock nodes are connectedto student nodes as well. Student nodes are only connected to docks under thefollowing conditions: (i) the dock is connected to at least one of the eventsthe student needs to attend and (ii) the student is free from pre–assignmentsin time–quanta represented by the dock and the dures consecutive time quanta.The event es is the shortest event enrolled by the student that can be held in theaforementioned dock, and its duration is denoted dures

. To each of the graph’sedges, a pheromone concentration value τij and a heuristic information valueηij are assigned. The LETP solution is a timetable with all of the events andstudents scheduled into the appropriate docks. A candidate solution (timetable)is represented as a subset of edges of the construction graph, connecting thetimetable building blocks into a specific timetable.

For larger problem instances, the size of the construction graph can be con-siderable, and the efficiency of the search procedure strongly depends on the sizeof the graph. To reduce the size of the search space, an additional preprocessingstep is performed. During that step, edges representing solution components ofpoor quality are removed. More precisely, an edge is removed if the number ofstudents who can attend the corresponding event is less than 80% of the roomcapacity. Note that this value may vary in different problem instances. In thefinal step, all isolated docks are removed.

Hard constraints are included in the construction procedure through theconstraint fence layer. This layer dynamically masks the edges of the constructiongraph that lead to infeasible solutions, based on each incomplete solution (partialtour) of the ants. Thus, ants moving through the graph are producing onlyfeasible timetables. The construction graph is a very large structure, while theconstraint fence is a small and expandable one. Ants access the graph exclusivelythrough the constraint fence. They may move only on paths that are allowedby the constraint fence, and they behave as if the edges that are not allowed bythe constraint fence did not exist at all. While the construction graph remainsconstant throughout the execution time, each ant that is moving through thegraph is given its own instance of the constraint fence. The constraint fenceevaluates each edge based on the desired set of timetable constraints. Each ofthe constraints from our library is implemented as an independent module. Thismakes it easy to update the constraints and to add new ones if needed. Thecomputational cost of the constraint fence depends on the set of constraintsused. If used with our current library, its computational complexity is O(|R|),where R is the set of rooms in the LETP instance.

Arti�cial Intelligenceexercise 1

Electrical Circuitsexercise

Databasesexcercise 4

Room A101Monday, April 21, 2008.

8:45 AM - quantum 3

Room D372Wednesday, April 23, 2008.

6:00 AM - quantum 136

PC Lab 1Friday, April 25, 2008

12:30 PM - quantum 210

Mechatronics laboratory,Wednesday, April 30, 200811:00 PM - quantum 448

Student 1

Student 2

Student 3

Student 4

Student (n-1)

Event node

Dock node

Student node

Legend:

Student n

Mechatronics laboratory,Friday, April 25, 2008

12:30 PM - quantum 210

Fig. 1. LETP construction graph. Edges represent partial assignments of students andevents to times and rooms. Note that the construction graph is not fully connected assome of the edges are implicit and implemented in the tour construction procedure.

3.2 Algorithm Description

Our approach uses a MAX −MIN Ant System [3], since such systems haveshown great promise on various different problems, including artificially gener-ated timetabling problems [5]. A colony of m ants is used. At each algorithmiteration, each ant constructs a complete timetable (a candidate solution). Ineach of the generated solutions, all of the hard constraints are satisfied.

In choosing solution components, the probability pkij that the ant k, currentlyat node i will choose the node j is calculated using the random proportional rulegiven by

pkij =[τij ]

α [ηij ]β

Σl∈Nki

[τil]α [ηil]

β, j ∈ N k

i , (1)

where τij is the pheromone trail value on the edge connecting node i tonode j, ηij is the heuristic value of that edge, α and β are the parameters whichdetermine the relative influence of pheromone trail and the heuristic information,and N k

i is the feasible neighbourhood of ant k when it is at node i.The pheromone trail between dock node i and event/student node j marks

the desirability of scheduling that event/student in that dock. In each algorithmiteration only one of the ants updates the pheromone trails based on the qualityof the constructed solution candidate. The heuristic value ηij is controlled by

the constraint fence for each ant. It is important to note that the heuristic valueis dynamically modified throughout the algorithm execution. It is set to zerowhen it is determined that the constraints of the problem would be violated ifthe edge (i, j) were included in the the tour, and to one otherwise.

Solutions are constructed one event at a time and the scheduling of each eventis performed in two phases. In the first phase, the event is placed into suitablerooms and time–slots. This is done by assigning a sufficient number of docks tothe event, one dock at a time, until a sufficient amount of room is reserved forthe event. The decision of which dock to assign to the event is a biased randomchoice that is influenced by the pheromone trail in the feasible neighbourhood ofthe event node. To determine the probability that an edge will be selected, therandom proportional rule is used. In the second phase of the scheduling of theevent, students are assigned to the docks chosen in the first phase. The decision ofwhich student is to be placed in which dock is also biased by the pheromone trailsdeposited by previous ant generations, using the random proportional rule. Aftera partial timetable for a single event is constructed, the ant constructs partialtimetables for all of the events that have not yet been scheduled. The order inwhich the ants schedule the events is heuristically determined at the start of eachiteration of the algorithm, so that the events with more unscheduled students inthe best tour of the previous iteration have greater priority. Each of the solutionsproposed by the ants is improved using the local search routine. The local searchrearranges the students among the docks assigned to the same event. It tries tofind suitable docks for students that are not scheduled to the event they need toattend. The search is performed by checking whether room can be made by foran unscheduled student by switching one of the scheduled students into anotherdock.

After the solution construction and local search is finished for all ants, eachof the solutions is evaluated. We define the penalty function as the total numberof unscheduled obligations in a candidate solution (the exact definition of anobligation is given in Section 3.3). The number of unscheduled obligations is alsoused as the optimised variable. After the evaluation, the pheromone updatingstep is performed as described in the following subsection.

3.3 Pheromone Update

The pheromone trail value is updated at the end of each algorithm iteration.The pheromone is updated by the best–so–far ant or the iteration–best ant. Theprobability that the best–so–far ant is allowed to update the pheromone trail is5%. Unlike usual ACO approaches, the pheromone gain value in our approach isnot the same for all of the edges of a single tour. Instead, the pheromone gain isdefined for each event individually. The quality value is assigned to each eventof the timetable by counting the number of obligations left unscheduled for thatevent. The intention is to improve the search process by using the quality of thesolution components to determine the pheromone gain value for individual edgesin the solution suggestion.

Usually, more than one event can be scheduled in a single dock. Nevertheless,after event e is scheduled in dock d, no other event can be scheduled into d.Therefore, the quality of a partial schedule of a single event cannot be measuredwithout considering its influence on other events. For example, suppose thatevent e1 can be scheduled in the set of docks {d0, d1, d2} and event e2 can bescheduled only in dock d1. Dock d1 may seem to be appropriate for event e1 sinceit would leave zero students that need to attend e1 unscheduled. However, this isa very poor choice considering that d1 is the only suitable dock for e2, so assigningit to e1 would leave all of the students who need to attend e2 unscheduled.The level of influence between two events is modelled by the influence functionf : E × E → [0, 1]. When fa,b = 0, event a has no influence on event b, whilefa,b = 1 means that event a is scheduled in the entire set of docks suitable forthe event b. More formally, the influence of event a on b, denoted fa,b, is definedas:

fa,b =|chosenDa ∩Db|

|Db|,

where chosenDa ⊆ Da is a subset of docks in which event a is scheduled in agiven suggested solution, and Db ⊆ D is the set of docks suitable for the eventb.

We use the number of unscheduled obligations as the optimised variable. Anobligation is defined as an assignment of a given student to one of the laboratoryexercises he or she needs to attend. In our problem representation, this is done byassigning students to the dock nodes during the second phase of the constructionprocedure for a single event, as described in Section 3.2. The solution qualityfunction Qe for the event e and the solution suggestion Sug is defined as:

Qe =assignedObligations(e,Sug)

numberOfObligations(e)· spaceEfficiency(e,Sug)3 ,

spaceEfficiency(e,Sug) =[

assignedObligations(e,Sug)reservedSeats(e,Sug)

].

The space efficiency factor ensures that better solutions use the dock space moreefficiently. The pheromone gain for each event ∆τe is given by

∆τe =

∑ei∈E

(fe,ei ·Qei)

|E|

4

, e ∈ E .

The pheromone gain ∆τe is deposited on the edges of the tour connecting theevent e to the dock d and on the edges connecting a student s to any of thedocks in which the event is scheduled.

3.4 MAX −MIN Ant System Parameters

Several configurations of the metaheuristic were evaluated, and the best resultswere achieved using the settings in Table 1. The pheromone values are initially

set to τmax. The pheromone trails are updated after each algorithm iteration,as described in Section 3.3, and evaporation is used for each edge, according tothe rule τij ← (1− ρ) · τij .

Our system uses either 10000 iterations or penalty = 0 as the stop criteria.To prevent stagnation, if the best solution found is not improved after 125 con-secutive iterations, the pheromone trails are reset by setting pheromone valueon each edge back to τmax.

Table 1. Ant colony optimisation algorithm parameters

Parameter Value Parameter Value

number of ants (m) 5 ρ 0.02α 1.0 τmax = 1/ρ 50β 1.0 τmin 0.5

4 Results

The system described here was successfully applied to the laboratory exercisestimetabling problem at the authors’ institution. The performance of the algo-rithm on several datasets is presented in Table 2. These problem instances havedifferent durations and widely varying numbers of events and attending stu-dents. Two values, Se,s and Ts are given as measures of the problem instancecomplexity. The student event sum, denoted Se,s, is defined as the aggregatenumber of events that each of the students needs to attend. More formally,Ss,e =

∑s∈S |Es|, where Es is the set of events that student s needs to at-

tend. The timespan of the problem instance, denoted Ts, is defined as thenumber of days on which the events need to be scheduled. For each dataset,30 independent runs were performed, and each run was limited to one hour.For the purpose of comparison, the maximum run–time limit is added to theusual stop criteria described in Section 3.4. Note that these datasets are in-stances of real–world timetabling problems that had appeared at our faculty.Anonymised version of these datasets is publicly available for download at http://morgoth.zemris.fer.hr/jagenda. To illustrate the effectiveness of our ap-proach, the results are compared with a GRASP technique (Table 2). The testedGRASP technique uses a construction search (different from the search proce-dure defined for our ants) to build solutions satisfying hard constraints, afterwhich a local search that optimises the schedule of students is performed. Weused the Mann–Whitney test to check the H0 hypothesis that the distributionfunctions of the algorithm performances were the same for the results of both theACO and GRASP techniques. For each of the datasets, the p values were wellbelow 0.05. On each problem instance, with very high statistical significance, weconclude that the ACO technique performs better than the GRASP technique.

Note that although the Genetic algorithm has also been applied to the LETPproblem as a part of a sister project at our institution [2], the performance ofthese approaches cannot be directly compared since different quality measuresand optimised variables are used in these approaches.

Table 2. Algorithm performance on different laboratory exercise timetabling probleminstances.

ACO penalty median comparison

instance Ss,e Ts min max st.dev. (σ) ACO GRASP

C1 2104 5 66 150 23.31 102 330

C2 7081 9 1 14 3.46 8 71

C4 4868 5 5 73 12.42 13 125

C8 5430 4 34 146 31.00 58 190

C12 5934 5 32 78 9.31 41 333

In some problem instances, a solution where all students are scheduled couldnot be found. This was usually caused by a constellation of conflicting events,or events with infeasible requirements posed by the course organisers. In suchinstances, the system is used as a tool for identifying the problematic events. Inpractice, the process of scheduling is usually an iterative process of querying thesystem for the best results, interpreting those results, and allowing the staff tomake informed decisions.

5 Conclusion

This paper presents a case study of applying ACO metaheuristic for solving acomplex large–scale timetabling problem at our institution. Our solution usesa relatively general problem representation, suitable for different types of in-stitutions. We present an innovative, memory–efficient problem representationthat is appropriate for large problem instances. Moreover, the modular designof the constraint library facilitates the addition of new constraints. It makesthe system manageable, which is extremely important for practical timetablingapplications. The exact problem we are solving is formulated as the laboratoryexercise timetabling problem, a subset of the university course timetabling prob-lem.

This work arose out of the specific timetabling needs of one institution. How-ever, the approach described here is not limited to LETP, since it shares manycommonalities with other UCTP instances. Thus, it is likely that the challengeswe faced, such as reducing the memory footprint of the construction graph orensuring the ease of adaptation to problem modifications, will also be faced byother researchers. Other authors may use our approach without modifying the

problem representation. The only necessary adaptation may be the implemen-tation of additional constraints that are not supported by our current library.

Furthermore, since prior work on ant colony optimisation mainly consid-ered artificially generated UCTP instances, our work proves that ACO can behighly successful in solving real–world timetabling problems. It is an effort tohelp bridge the gap between theoretical research and practical adaptation ofmetaheuristic techniques that is currently so prevalent in the area of automatedtimetabling. Our work can also be viewed as an additional confirmation thatACO is not only an interesting academic research topic, but also a manageableand efficient approach able to solve highly complex real–world problems.

References

1. Cooper, T.B., Kingston, J.H.: The complexity of timetable construction problems.In: Proceedings of the First International Conference on the Practice and Theoryof Automated Timetabling (ICPTAT ’95). (1995) 511–522

2. Bratkovic, Z., Herman, T., Omrcen, V., Cupic, M., Jakobovic, D.: University coursetimetabling with genetic algorithm: A laboratory excercises case study. In Cotta,C., Cowling, P., eds.: Proceedings of EvoCOP 2009 - 9th European ConferenceEvolutionary Computation in Combinatorial Optimization. Volume 5482 of LectureNotes in Computer Science., Springer, Heidelberg (2009) 240–251

3. Dorigo, M., Stutzle, T.: Ant Colony Optimization. Bradford Books. The MIT Press(july 2004)

4. Socha, K., Sampels, M., Manfrin, M.: Ant Algorithms for the University CourseTimetabling Problem with Regard to the State-of-the-Art. In: Proceedings of Evo-COP 2003 – 3rd European Workshop on Evolutionary Computation in Combina-torial Optimization. Volume 2611 of Lecture Notes in Computer Science., SpringerVerlag, Berlin, Germany (2003) 334–345

5. Socha, K., Knowles, J., Sampels, M.: A MAX -MIN Ant System for the UniversityTimetabling Problem. In Dorigo, M., G. Di Caro, Sampels, M., eds.: Proceedings ofANTS 2002 – From Ant Colonies to Artificial Ants: Third International Workshopon Ant Algorithms. Volume 2463 of Lecture Notes in Computer Science., SpringerVerlag, Berlin, Germany (September 2002) 1–13

6. Rossi-Doria, O., Sample, M., Birattari, M., Chiarandini, M., Dorigo, M., Gam-bardella, L., Knowles, J., Manfrin, M., Mastrolilli, M., Paechter, B., Paquete, L.,Stutzle, T.: A Comparison of the Performance of DifferentMetaheuristics on theTimetabling Problem. In: The Practice and Theory of Automated Timetabling IV:Revised Selected Papers from the 4th International conference, Gent 2002. Volume2740 of Springer Lecture Notes in Computer Science., Springer, Berlin, Germany(2003) 329–351

7. Azimi, Z.: Comparison of Methheuristic Algorithms for Examination TimetablingProblem. Applied Mathematics and Computation 16(1) (2004) 337–354

8. McCollum, B.: University timetabling: Bridging the gap between research and prac-tice. In E Burke, H.R., ed.: PATAT 2006 — Proceedings of the 6th internationalconference on the Practice And Theory of Automated Timetabling, Masaryk Uni-versity (2006) 15–35

9. Gross, J.L., Yellen, J.: A Handbook of Graph Theory. Discrete Mathematics andIts Applications. CRC books (December 2003)