Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10711Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.date.accessioned | 2015-11-24T17:00:07Z | - |
| dc.date.available | 2015-11-24T17:00:07Z | - |
| dc.identifier.issn | 0020-0255 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10711 | - |
| dc.rights | Default Licence | - |
| dc.subject | hypercube | en |
| dc.subject | gray-code labeling | en |
| dc.subject | recognition | en |
| dc.subject | graph partition | en |
| dc.subject | parallel algorithms | en |
| dc.subject | complexity | en |
| dc.title | Optimal Gray-code labeling and recognition algorithms for hypercubes | 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 | 2001 | - |
| heal.abstract | We present an optimal greedy algorithm which returns a Gray-code labeling of the nodes of an n-dimensional hypercube, that is, a labeling of the nodes with binary strings of length n for which the Hamming distance between two nodes is I if and only if these are adjacent in the hypercube. The proposed algorithm is very simpler it uses breadth-first search to guide the greedy choice of nodes and computes the Gray-code label of a node u by performing the logical disjunction of the Gray-code labels of two nodes adjacent to node u. It takes as input a hypercube Q(n) with N = 2(n) nodes and runs in O(N logN) time. Based on the labeling algorithm we propose a recognition algorithm for hypercubes which runs in O(N log N) time. Thus, in view of the fact that Q(n) has n2(n-1) edges, this behaviour is optimal. Both labeling and recognition algorithms incorporate such algorithmic features that they can be optimally implemented in a PRAM model of computation. (C) 2001 Elsevier Science Inc. All rights reserved. | en |
| heal.journalName | Information Sciences | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nikolopoulos-2001-Optimal Gray-code labeling and recognition algorithms for hypercubes.pdf | 288.12 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
