¿Dónde me siento? Digrafos amigo-enemigo.
Los invitamos a un nuevo encuentro del seminario de grafos, el próximo lunes 27/04 a las 14 hs. en la sala de reuniones 2119 del Pabellón 0+infinito.
Expositor: Ayelén Alcantar
Título: ¿Dónde me siento? Digrafos amigo-enemigo.
Resumen:
Imaginemos un grupo de personas con relaciones de amistad y enemistad. ¿Podemos ubicarlas en el espacio de modo que cada una quede más cerca de sus amigos que de sus enemigos? Esto es el problema "Sitting Closer to Friends than Enemies", estudiado en grafos.
En esta charla extendemos el problema al mundo de los digrafos signados, donde las relaciones pueden ser asimétricas. Esto abre dos variantes naturales: ¿querés estar cerca de quienes vos considerás amigos, o de quienes te consideran amigo a vos?
Vamos a caracterizar cuándo un digrafo completo admite solución en la recta real y en la circunferencia. Analizamos la complejidad computacional del problema en digrafos generales y veremos que, si bien en general es difícil, hay clases de digrafos donde el problema se vuelve tratable.
Son todos bienvenidos y si están interesados en participar frecuentemente en este seminario, los invitamos a unirse a nuestro grupo de Telegram: https://t.me/+
