Have1 and Liebl [1973], and Leighton 119841.' The networks of interest are defined in section 1.3.' For any graph 53, we denote by (%I the number of nodes in %.

Article Free Access Share on Optimal simulations by Butterfly Networks Authors: Sandeep Bhatt Department of Computer Science, Yale University, New Haven, CT Department of Computer Science, Yale University, New Haven, CTView Profile , Fan Chung Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJ Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJView Profile , Jia-Wei Hong Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NY Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NYView Profile , Arnold Rosenberg Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 192–204https://doi.org/10.1145/62212.62229Published:01 January 1988Publication History 24citation283DownloadsMetricsTotal Citations24Total Downloads283Last 12 Months20Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H.There are two natural measures of the cost of a graph embedding, namely, the dilationcost of the embedding: the maximum distance in H between the images of vertices that are adjacent in G; and the expansion-cost of the embedding: the ratio of the size of H to the size of G.The main results of this paper illustrate three situaUons wherein one of these costs can be minimized only at the expense of a dramatic increase in the other cost.The first result establishes the following: There is an embedding of n-node complete ternary trees in complete binary trees with dilation-cost 2 and expansion cost O(n~), where ~ = 1og3(4/3); but any embedding of these ternary trees in binary trees that has expansion-cost c < 2 must have dilation-cost G(logloglogn).The second result provides a stronger but less easily stated example of the same type of trade-off.The third result concerns generic binary trees, that is, complete binary trees into which all n-node binary trees are "efficiently" embeddable.There is a generic binary tree into which all n-node binary trees are embeddable with dilauon-cost O(1) and expansion-cost O(n ~) for some fixed constant c; if one insists on embeddings whose dilation-cost is exactly 1, then these embeddings must have expansion-cost f~(n¢~°*~)/~); tf one insists on embeddmgs whose expansion-cost is less than 2, then these embeddings must have dilation cost ~(log log log n) An interesting application of the polynomial size genenc binary tree m the first part of this three-part result is to yield simplified proofs of several results concerning computational systems with an intrinsic nouon of "computation tree," such as alternating and nondeterministic Turing machines and context-free grammars.

In this paper we give a complete problem in ${\text{DSPACE}}(n)$. The problem is whether there exists a cycle in the connected component containing $(0,0, \cdots ,0)$ in the graph $G_p $ of the zeros of a polynomial P over $GF(2)$ under a suitable natural coding. Hence the deterministic space complexity of this problem is $O(n)$ but not $o(n)$. We give as well several problems for which we can obtain very close upper and lower deterministic space bounds. For example, the deterministic space complexity to determine whether there exists a cycle in the graph of the set of assignments satisfying a Boolean formula is $O(n/\log n)$ but not $o(n/\log ^2 n)$.

This paper studies embeddings of graphs in binary trees. The cost of such an embedding is the maximum distance in the binary tree between images of adjacent graph vertices. Several techniques for bounding the costs of such embeddings from above are derived; notable among these is an algorithm for embedding any outerplanar graph in a binary tree with a cost that is within a factor of 3 of optimal. A number of techniques for bounding the costs of such embeddings from below are developed; notable here are two techniques for inferring the presence of large separators in graphs. Finally, a number of characterizations are established of those families of graphs that are almost binary trees, in the sense that every graph in the family is embeddable in a binary tree within bounded cost.

In this paper, the red-blue pebble game is proposed to model the input-output complexity of algorithms. Using the pebble game formulation, a number of lower bound results for the I/O requirement are proven. For example, it is shown that to perform the n-point FFT or the ordinary n×n matrix multiplication algorithm with O(S) memory, at least Ω(n log n/log S) or Ω(n3/@@@@S), respectively, time is needed for the I/O. Similar results are obtained for algorithms for several other problems. All of the lower bounds presented are the best possible in the sense that they are achievable by certain decomposition schemes.

This paper studies embeddings of graphs in binary trees. The cost of such an embedding is the maximum distance in the binary tree between images of adjacent graph vertices. Several techniques for bounding the costs of such embeddings from above are derived; notable among these is an algorithm for embedding any outerplanar graph in a binary tree with a cost that is within a factor of 3 of optimal. A number of techniques for bounding the costs of such embeddings from below are developed; notable here are two techniques for inferring the presence of large separators in graphs. Finally, a number of characterizations are established of those families of graphs that are almost binary trees, in the sense that every graph in the family is embeddable in a binary tree within bounded cost.

In this paper we give a complete problem in DSPACE(n). The problem is whether there exists a cycle in the connected component containing (o,o,...,o) in the graph Gp of the zeroes of a polynomial P over GF(2) under a suitable natural coding. Hence the deterministic space complexity of this problem is O(n) but not o(n). We give as well several problems for which we can obtain very close upper and lower deterministic space bounds. For example, the deterministic space complexity to determine whether there exists a cycle in the graph of the set of assignments satisfying a Boolean formula is O(n/log n) but not o(n/log2n).