Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11149Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.date.accessioned | 2015-11-24T17:03:17Z | - |
| dc.date.available | 2015-11-24T17:03:17Z | - |
| dc.identifier.issn | 0020-0190 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11149 | - |
| dc.rights | Default Licence | - |
| dc.subject | cographs | en |
| dc.subject | threshold graphs | en |
| dc.subject | edge classification | en |
| dc.subject | graph partition | en |
| dc.subject | recognition | en |
| dc.subject | parallel algorithms | en |
| dc.subject | complexity | en |
| dc.subject | recognition algorithm | en |
| dc.subject | parallel recognition | en |
| dc.title | Recognizing cographs and threshold graphs through a classification of their edges | 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 | 2000 | - |
| heal.abstract | In this work, we attempt to establish recognition properties and characterization for two classes of perfect graphs, namely cographs and threshold graphs, leading to constant-time parallel recognition algorithms. We classify the edges of an undirected graph as either free, semi-free or actual, and define the class of A-free graphs as the class containing all the graphs with no actual edges. Then, we define the actual subgraph G(a) of a non-A-free graph G as the subgraph containing all the actual edges of G. We show properties and characterizations for the class of A-free graphs and the actual subgraph G(a) of a cograph G, and use them to derive structural and recognition properties for cographs and threshold graphs. These properties imply parallel recognition algorithms which run in O(1) time using O(nm) processors. (C) 2000 Elsevier Science B.V. All rights reserved. | en |
| heal.journalName | Information Processing Letters | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nikolopoulos-2000-Recognizing cographs and threshold graphs through a classification of their edges.pdf | 151.95 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
