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.