El grupo de Algoritmos y Combinatoria del CMM se centra en la comprensión de los aspectos estructurales de los grafos, los algoritmos centralizados y distribuidos, y el comportamiento de ciertos procesos en redes. Nuestras líneas de investigación principales se describen a continuación.
Nos interesa la teoría de grafos estructural, extremal y algorítmica. Nuestros temas incluyen problemas de tipo Ramsey y problemas de contención de árboles, así como regularidad de grafos. Otros temas más interdisciplinarios son las propiedades geométricas clásicas en el contexto de espacios métricos inducidos por grafos finitos, y temas en la frontera entre la teoría de grafos y la teoría de grupos.
Nos interesan las estructuras y procesos aleatorios discretos, así como las aplicaciones de esta investigación a problemas de combinatoria e informática. En concreto, nuestra investigación abarca temas como modelos de redes complejas, difusión de información en redes, grafos aleatorios, pruebas de propiedades y algoritmos de tiempo sublineal.
La computación distribuida se refiere a un conjunto de procesadores que colaboran para realizar una tarea global. Cualquier algoritmo distribuido debe lidiar, al menos, con las siguientes dos restricciones: (1) la falta de conocimiento sobre procesadores remotos; (2) la limitación de recursos disponibles, como tiempo, memoria local y comunicación (ancho de banda). Además de diseñar algoritmos distribuidos eficientes, nos interesa obtener límites inferiores y resultados de imposibilidad.
El grupo de Concepción trabaja en redes booleanas, autómatas celulares y dinámica de máquinas de Turing.
