Talleres IMC: Contando órdenes conexos de vértices en grafos
11 de Junio, 2026
El Instituto de Ingeniería Matemática y Computacional (IMC) invita a la nueva edición de sus Talleres que se realizará el miércoles 17 de junio.
Miércoles 17 de junio de 2026, 13:40 hrs. (Presencial en sala segundo piso (DILAB), Edificio Carreras Interdisciplinarias).
ABSTRACT
Un orden de los vértices de un grafo se dice conexo si cada vértice en el orden, excepto el primero, está conectado con alguno de los vértices anteriores. Tales órdenes existen para un grafo si, y solo si, el grafo es conexo; por lo tanto, en términos de decisión, este problema puede resolverse de manera eficiente. En esta charla, mostraremos que el problema de contar el número de órdenes conexos de los vértices de un grafo es difícil. En particular, mostraremos que es #P-completo. Además, discutiremos brevemente lo que sabemos sobre la posibilidad de aproximar eficientemente este problema de conteo.
BIO
Profesor Departamento de Ciencia de la Computación de la Pontificia Universidad Católica de Chile/Instituto de Ingeniería Matemática y Computacional UC, Doctor en Ciencia de la Computación de la Universidad de Toronto, Canadá. Fue director hasta 2023 del Instituto Milenio Fundamentos de los Datos (IMFD) y, anteriormente, fue también director del Centro de Investigación de la Web Semántica (CIWS), que luego diera origen al actual IMFD.
