Keywords
Independent Set
Operations Research
Educational Timetabling
Calendarización
Conjunto Independiente
Investigación de Operaciones
Teoría de Gráficas
How to Cite
Abstract
Registration process at the Universidad Aut´onoma Metropolitana is such that every student is free to choose his/her own subjects and schedule. Success of this system, based in the percentage of students that obtain a place in the lectures chosen, depends principally on the characteristics of the supply of scheduled lectures, relatives to quantity and variety of timetables, as well as the oportunity of the students to do an adequate selection of lectures. An adequate selection of lectures is a subset of the lectures set with pairwise different subjects and timetables. The Choose Lectures Problem is to find the maximal adequate selection of lectures. A Graph Theory model of the problem and an algorithm to solve it will be shown.
References
Bergé, C. (1970) Graphes et Hypergraphes. Dunod, París.
Bron, C; Kerbosch, J. (1973) “Algorithm 457: Finding all cliques of an undirected graph”, Commun. ACM 161: 575–577.
Christofidès, N. (1975) Graph Theory: An Algorithmic Approach. Academic Press, New York.
Füredi, Z. (1987) “The number of maximal independent sets in connected graph”, Journal of Graph Theory 11(4): 463–470.
Garey, M.R.; Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. Publishers, San Francisco.
Golumbic, M.C. (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
Griggs, J.R.; Grinstead, C.M., Guichard, D.R. (1988) “The number of maximal independent sets in a connected graph”, Discrete Mathematics 68: 211–220.
Gutiérrez-Andrade, M.A. (1991) La Técnica de Recocido Simulado. Tesis de doctorado, UNAM, México.
Hammer, P.L.; Mahadev, N.V.R., de Werra, D. (1985) “Stability in CAN-free graphs”, Journal of Combinatorial Theory, Series B 38: 23–30.
Harary, F. (1972) Graph Theory. Addison Wesley, Reading, MS.
López-Bracho, R.; Ortuño-Sánchez, M.P. (2000) “Un algoritmo paralelo para el problema del conjunto independiente”, Revista de Matemática: Teoría y Aplicaciones 7(1-2): 125–134.
Neumann-Lara, V. (1985) “Introducción a la Teoría de Gráficas”, IV Coloquio del Departamento de Matemáticas del CINVESTAV, México.
Papadimitriou, C.H.; Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice Hall Inc., Englewood Cliffs, N.J.
Syslo, M.; Deo, N.; Kowalik, J. (1983) Discrete Optimization Algorithms with Pascal Programs. Prentice Hall Inc., Englewood Cliffs, N.J.