Palabras clave
Independent Set
Operations Research
Educational Timetabling
Calendarización
Conjunto Independiente
Investigación de Operaciones
Teoría de Gráficas
Cómo citar
Resumen
El proceso de inscripción para alumnos de la Universidad Autónoma Metropolitana tiene como fundamento la libertad de cada alumno de seleccionar las asignaturas que cursará, así como los grupos en los que quedará inscrito. El éxito de este sistema, medido en términos del porcentaje de alumnos que obtienen inscripción en los cursos que seleccionaron, depende en gran medida tanto de las características de la oferta de grupos, relativas principalmente a la cantidad y a la variedad de horarios, como de la posibilidad por parte de los alumnos de hacer una selección adecuada de horarios para los cursos por los que optaron. Una selección adecuada de horarios de cursos es aquella en la que las asignaturas seleccionadas tienen horarios dos a dos compatibles. El problema de selección de horarios consiste en la obtención de una selección de horarios adecuada de cardinalidad máxima. En este trabajo se presentará un modelo de Teoría de Gráficas para este problema así como un algoritmo de solución para el mismo.
Citas
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.