Characterizing and computing minimal cograph completions (Journal article)

Papadopoulos, C./ Lokshtanov, D./ Mancini, F.

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 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.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
ISSN: 0166-218X
Publisher: Elsevier
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Papadopoulos-2010-characterizing and computing.pdf270.89 kBAdobe PDFView/Open    Request a copy

 Please use this identifier to cite or link to this item:
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.