Evaluación 2016 Invierno

Deberán escoger un artículo de estas columnas. De ese artículo deben escoger dos problemas. De esos dos problemas deben escribir un reporte de entre 4 y 5 páginas con la definición de sus problemas y la prueba de que cada uno de esos problemas es NP completo. Para ello tal vez deban definir dos problemas más (aquellos con los que se hace la reducción polinomial). Su reporte debe estar hecho en LaTeX e incluir todas las referencias usadas (sólo artículos, no usen otro tipo de referencias). Adicionalmente, deberán hacer una presentación en clase de 20 minutos acerca de uno de los dos problemas escogidos. La fecha de su presentación aparece en la tabla de abajo. La fecha de entrega del reporte es el 6 de abril.

Nota importante: Todos deben asistir a todas las presentaciones, su calificación depende de esto.

Fecha de presentación
 Alumno
 Columna
 Problema 1
 Problema 2
30 de marzo
 Gabriel Espinosa 9
 Latin Squares Pebble Game
30 de marzo
 Ivonne Gómez
 1
 Chordal Graph Completion
 Chromatic Index
30 de marzo
 Eduardo Miranda
 3
 Edge-Partition into Triangles Geometric Covering by Discs
4 de abril Juan Gutiérrez
 4
 #1-5
 #6-7
4 de abril Héctor Marín
 2
 Graph Thickness Minimum Area Embedding of Planar Graph
4 de abril Christopher Amezcua
 5
 Bus Routing
 Delivery Van Routing
6 de abril
 Gicela Montero
8
 Deadlock Avoidance
 Unsafe Locking Policy
6 de abril
 Mauricio Praxedis
 6
 Graceful/Harmonious Graphs
 Simultaneous Diophantine Approximation
6 de abril
 Saúl Martínez
 14
 Degree Constrained Subgraph
 #