Séminaire

We study here a survey on some practical recursive algorithms on graphs, trying to understand on which problems a linear complexity can be achieved or not (showing a lower bound).
Problems considered include minimizing deterministic automaton, modular decomposition and computation of canonical vertex partition (also called Weisfeiler-Leman graph isomorphism test).
We focus on  a linear time modular decomposition for graphs and extract from it an interesting recursive framework that can be used for other problems such as transitive orientation or circular graph recognition ...