Name
Abstract | ||
|---|---|---|
A cograph completion of an arbitrary graph G is a cograph supergraph of G on the same vertex set. Such a completion is called minimal if the set of edges added to 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 of an arbitrary input graph G in 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 FAW'08-2nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147158. [1]]. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.dam.2009.01.016 | Discrete Applied Mathematics |
Keywords | Field | DocType |
linear-time algorithms,vertex incremental algorithm,minimal cograph completion h,arbitrary graph,cographs,cograph completion,minimal completions,minimal cograph completion,vertex set,arbitrary input graph,linear time,cograph supergraph,algorithmics workshop | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Cograph,Epigraph,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
158 | 7 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.47 | 36 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Lokshtanov | 1 | 1438 | 110.05 |
| Federico Mancini | 2 | 78 | 9.79 |
| Charis Papadopoulos | 3 | 151 | 17.75 |