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: | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών |
URI: | https://olympias.lib.uoi.gr/jspui/handle/123456789/12619 |
ISSN: | 0166-218X |
Link: | http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-352.pdf |
Publisher: | Elsevier |
Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Papadopoulos-2010-characterizing and computing.pdf | 270.89 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
This item is a favorite for 0 people.
https://olympias.lib.uoi.gr/jspui/handle/123456789/12619
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.