Recognizing cographs and threshold graphs through a classification of their edges
| 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.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.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.journalName | Information Processing Letters | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2000 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: