Séminaire Algorithmique : « Commit graphs in Version-Control Systems: incremental reachability and label discovery », Euxane Tran-Girard (LIGM, Univ. Paris-Est G. Eiffel)

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.
Our approaches perform competitively in practice upon evaluation on our newly released dataset of real-world graphs.