Optimal Gray-code labeling and recognition algorithms for hypercubes
| 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.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.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.journalName | Information Sciences | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2001 | - |
| 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
- Περιγραφή: