Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/10711
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNikolopoulos, S. D.en
dc.date.accessioned2015-11-24T17:00:07Z-
dc.date.available2015-11-24T17:00:07Z-
dc.identifier.issn0020-0255-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/10711-
dc.rightsDefault Licence-
dc.subjecthypercubeen
dc.subjectgray-code labelingen
dc.subjectrecognitionen
dc.subjectgraph partitionen
dc.subjectparallel algorithmsen
dc.subjectcomplexityen
dc.titleOptimal Gray-code labeling and recognition algorithms for hypercubesen
heal.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικήςel
heal.publicationDate2001-
heal.abstractWe 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.journalNameInformation Sciencesen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)



This item is licensed under a Creative Commons License Creative Commons