# WEEKLY ACTIVITIES

Faster and Enhanced Inclusion-Minimal Cograph Completion
 Speaker: Chritophe Crespelle (University Lyon)Time: 9h30, Thursday, December 21, 2017Location: 611-612, Building A6, Institute of Mathematics, 18 Hoang Quoc VietAbstract: We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in \$O(n+m')\$ time, where \$m'\$ is the number of edges in the completed graph. This matches the complexity of the algorithm in~\cite{LMP10} and positively answers one of their open questions.Our second algorithm improves the complexity of inclusion-minimal completion to \$O(n+m\log^2 n)\$ when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only \$O(n)\$ edges, require \$\Omega(n^2)\$ edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as \$O(n/\log^2 n)\$.joint work with Daniel Lokshtanov, Thi Ha Duong Phan and Eric Thierry

### Highlights

 29/11/21, Conference:Resolution of Singularities 01/12/21, Conference:Một số phương pháp cơ bản trong nghiên cứu định tính và tối ưu cho phương trình vi phân thường và phương trình đạo hàm riêng phi tuyến 02/12/21, Conference:Trường Tô pô và Lý thuyết kỳ dị 06/12/21, Conference:Workshop "Singularities, arrangements, and low-dim. topology" 15/12/21, Conference:Hội thảo thường niên về Xác suất và các chủ đề liên quan “Annual Conference on Probability and Related Topics ” 21/06/22, Conference:The 7th International Conference on Random Dynamical Systems 17/08/22, Conference:International Conference on Differential Equations and Applications