Người báo cáo: Chritophe Crespelle (University Lyon)
Thời gian: 9h30, ngày thứ 5, ngày 21 tháng 12 năm 2017
Địa điểm: Phòng 611 - 612, nhà A6, Viện Toán học, 18 Hoàng Quốc Việt
Tóm tắt: 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+mlog^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 |
