Posts classified under: Séminaire Algo

A graph is chordal if it has no induced cycle of length greater than 3. Alternatively, Dirac proved that a graph is chordal if and only if every minimal separator is a clique. From this characterization it is not hard to prove that a k-connected chordal graph can be uniquely decomposed into (k+1)-connected components by … Continue reading Séminaire Algorithmique : « Enumeration of some families of chordal graphs », Jordi Castellvi (Univ. Barcelone, Espagne)

Current distributed source version-control systems (such as Git and Mercurial), track the history of changes using an append-only directed acyclic graph, sometimes complemented by labels subsequently attached to commits. We present a chain-based and a dichotomy-based framework, both leveraging incremental indices, to answer reachability queries in sub-linear time, and efficiently perform label synchronisation between users. … Continue reading Séminaire Algorithmique : « Commit graphs in Version-Control Systems: incremental reachability and label discovery », Euxane Tran-Girard (LIGM, Univ. Paris-Est G. Eiffel)