OPTIMAL ROUTING OF PARENTHESES ON THE HYPERCUBE

Authors
MAYR EW WERCHNER R
Citation
Ew. Mayr et R. Werchner, OPTIMAL ROUTING OF PARENTHESES ON THE HYPERCUBE, Journal of parallel and distributed computing, 26(2), 1995, pp. 181-192
Citations number
33
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Journal of parallel and distributed computing → ACNP
ISSN journal
07437315
Volume
26
Issue
2
Year of publication
1995
Pages
181 - 192
Database
ISI
SICI code
0743-7315(1995)26:2<181:OROPOT>2.0.ZU;2-#
Abstract
We consider a new class of routing requests, or partial permutations, for which we give optimal on-line routing algorithms on the hypercube and shuffle-exchange network. For well-formed words of parentheses our algorithm establishes communication between all matching pairs in log arithmic time. It can be applied to the membership problem for certain subclasses of deterministic context-free languages, such as Dyck lang uages, and to a number of problems dealing with algebraic expressions. (c) 1995 Academic Press, Inc.