[Todos CMAT] ciclo de charlas ingeniería matemática (viernes 8, 16 hs)

[Laura Aspirot]

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.