[Todos CMAT] recordatorio charla Martín Matamala hoy a las 16:00

[Laura Aspirot]

---------- Mensaje reenviado ----------
De: Laura Aspirot <aspirot en fing.edu.uy>
Fecha: 5 de octubre de 2010 13:48
Asunto: ciclo de charlas ingeniería matemática (viernes 8, 16 hs)
Para: todos_imerl en fing.edu.uy, ingenieria.matematica en fing.edu.uy,
est_ing_mat en fing.edu.uy, todos en cmat.edu.uy


Estimados, comenzamos un pequeño ciclo de charlas de la Maestría en
Ingeniería Matemática de la Facultad de Ingeniería. Este viernes 8 de
octubre los invitamos a la charla del Prof. Martín Matamala
(Universidad de Chile). Será en el salón azul de la Facultad de
Ingeniería a las 16:00.

Abajo van título y resumen.
Saludos, Laura


Title: Reconstruction of 2 and 3-colored grids.

Martín Matamala, Dept. of Mathematical Engineering, Universidad de Chile.

Abstract.

In this talk I will present some results concerning
the computational complexity of the reconstruction
of colored grids (with 2 or 3 colors), from the total number of cells
of each color in each row and column.

I will give some ideas about how the reconstruction works for two colors,
and some conditions under which it works for three colors. I will
also give a sketch of the proof that for three colors the problem
is NP-complete. And, how this results leads to prove
some NP-completeness results for some tiling reconstruction and
graph reconstruction problems.