File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimal simulation of full binary trees on faulty hypercubes

TitleOptimal simulation of full binary trees on faulty hypercubes
Authors
KeywordsEmbedding
Hypercubes
Full binary trees
Dilation
Simulation
Issue Date1995
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tpds
Citation
Ieee Transactions On Parallel And Distributed Systems, 1995, v. 6 n. 3, p. 269-286 How to Cite?
AbstractThe problem of operating full binary tree based algorithms on a hypercube with faulty nodes was investigated. Developing a method for embedding a full binary tree into the faulty hypercube is the solution to this problem. Two outcomes for embedding an (n-1)-tree into an n-cube with unit dilation and load, that were based on a new embedding technique, were presented. For the problem where the root can be mapped to any nonfaulty hypercube node, the optimum toleration of faults was shown. Moreover, it was demonstrated that the algorithm for the variable root embedding problem is maximal within a class algorithms called recursive embedding algorithms as far as the number of tolerable faults is concerned. Lastly, it was demonstrated that when an O(1/√n) fraction of nodes in the hypercube are faulty, a O(1)-load variable root embedding is not always possible regardless of the significance of the dilation.
Persistent Identifierhttp://hdl.handle.net/10722/43631
ISSN
2015 Impact Factor: 2.661
2015 SCImago Journal Rankings: 1.590
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, Bethany MYen_HK
dc.contributor.authorChin, Francis YLen_HK
dc.contributor.authorPoon, ChungKeungen_HK
dc.date.accessioned2007-03-23T04:50:53Z-
dc.date.available2007-03-23T04:50:53Z-
dc.date.issued1995en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1995, v. 6 n. 3, p. 269-286en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43631-
dc.description.abstractThe problem of operating full binary tree based algorithms on a hypercube with faulty nodes was investigated. Developing a method for embedding a full binary tree into the faulty hypercube is the solution to this problem. Two outcomes for embedding an (n-1)-tree into an n-cube with unit dilation and load, that were based on a new embedding technique, were presented. For the problem where the root can be mapped to any nonfaulty hypercube node, the optimum toleration of faults was shown. Moreover, it was demonstrated that the algorithm for the variable root embedding problem is maximal within a class algorithms called recursive embedding algorithms as far as the number of tolerable faults is concerned. Lastly, it was demonstrated that when an O(1/√n) fraction of nodes in the hypercube are faulty, a O(1)-load variable root embedding is not always possible regardless of the significance of the dilation.en_HK
dc.format.extent1842549 bytes-
dc.format.extent25600 bytes-
dc.format.extent50917 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.format.mimetypeapplication/pdf-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_HK
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rights©1995 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.en_HK
dc.subjectEmbeddingen_HK
dc.subjectHypercubesen_HK
dc.subjectFull binary treesen_HK
dc.subjectDilationen_HK
dc.subjectSimulationen_HK
dc.titleOptimal simulation of full binary trees on faulty hypercubesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=6&issue=3&spage=269&epage=286&date=1995&atitle=Optimal+simulation+of+full+binary+trees+on+faulty+hypercubesen_HK
dc.identifier.emailChin, Francis YL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, Francis YL=rp00105en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/71.372776en_HK
dc.identifier.scopuseid_2-s2.0-0029267583en_HK
dc.identifier.hkuros1188-
dc.identifier.volume6en_HK
dc.identifier.issue3en_HK
dc.identifier.spage269en_HK
dc.identifier.epage286en_HK
dc.identifier.isiWOS:A1995QM58100004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, Bethany MY=7201530697en_HK
dc.identifier.scopusauthoridChin, Francis YL=7005101915en_HK
dc.identifier.scopusauthoridPoon, ChungKeung=7202673523en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats