Optimal Gray-code labeling and recognition algorithms for hypercubes
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Information Sciences
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Περιγραφή
Λέξεις-κλειδιά
hypercube, gray-code labeling, recognition, graph partition, parallel algorithms, complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής