Characterizing and computing minimal cograph completions ?
A cograph completion of an arbitrary graph G G is a cograph supergraph of G G on the same vertex set. Such a completion is called minimal if the set of edges added to G G is inclusion minimal. In this paper we present two results on minimal cograph completions. The first is a characterization that allows us to check in linear time whether a given cograph completion is minimal. The second result is a vertex incremental algorithm to compute a minimal cograph completion H H of an arbitrary input graph G G in O(|V(H)|+|E(H)|) O ( | V ( H ) | + | E ( H ) | ) time. An extended abstract of the result has been already presented at FAW 2008 [D. Lokshtanov, F. Mancini, C. Papadopoulos, Characterizing and computing minimal cograph completions, in: Proceedings of FAW082nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147158. [1]].
cographs minimal completions linear-time algorithms