Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/13487Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Papadopoulos, C. | en |
| dc.contributor.author | Heggernes, P. | en |
| dc.date.accessioned | 2015-11-24T17:28:01Z | - |
| dc.date.available | 2015-11-24T17:28:01Z | - |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/13487 | - |
| dc.rights | Default Licence | - |
| dc.title | Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2009 | - |
| heal.abstract | We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute. | en |
| heal.publisher | Elsevier | en |
| heal.journalName | Theoretical Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Papadopoulos-2009-single edge monotonic.pdf | 272.31 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
