[general_dat] Seminario de Grafos - Martes 4/11 a las 15 hs.

[Aye Alcantar]

Hola!

Este *martes 4 de noviembre a las 15 hs* nos reuniremos en la *sala 2119
del Pabellón 0+Infinito*. La próxima charla será presentada por *Amalia
Sorondo. *Les dejamos la información de la misma debajo.

*Título: *Extending Ghouila-Houri’s Characterization of Comparability Graphs
to Temporal Graphs.

*Resumen:*

An orientation of a given static graph is called transitive if for any
> three vertices a,b,c, the presence of arcs (a,b) and (b,c) forces the
> presence of arc (a,c). If only the presence of an arc between a and c is
> required, but its orientation is unconstrained, the orientation is called
> quasi-transitive. A fundamental result presented by Ghouila-Houri
> guarantees that any static graph admitting a quasi-transitive orientation
> also admits a transitive orientation. In a seminal work, Mertzios et al.
> introduced the notion of temporal transitivity in order to model
> information flows in simple temporal networks. We revisit the model
> introduced by Mertzios et al. and propose an analogous to Ghouila-Houri's
> characterization for the temporal scenario. We present a structure theorem
> that will allow us to express by a 2-SAT formula all the constraints
> imposed to a temporal graph for it to admit a temporal transitive
> orientation. The latter produces an efficient recognition algorithm for
> graphs admitting such orientations, that we will call T-comparability
> graphs. Inspired by the lexicographic strategy presented by Hell and Huang
> to transitively orient static graphs, we then propose an algorithm for
> constructing a temporal transitive orientation of a YES instance. This
> algorithm is straightforward and has a running-time complexity of
> max{O(nm), min{O(kn),O(m^2)}}, with k being the number of monolabel
> triangles in the temporal graph, i.e. triangles having the same unique
> time-label on their edges. This represents an improvement compared to the
> algorithm presented by Mertzios et al. Additionally, we extend the temporal
> transitivity model to temporal graphs having multiple time-labels
> associated to their edges and claim that the previous results hold in the
> multilabel setting. Finally, we propose a characterization of
> T-comparability graphs via forbidden temporal ordered patterns.



Aquellas personas interesadas en participar frecuentemente en
este seminario, son invitadas a unirse a nuestro grupo de Telegram:
https://t.me/+RkVxwjjIdiE1Yjkx y visitar la página del seminario:
https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos.

Esperamos puedan asistir.

Saludos,
-- 
Aye Alcantar