Cost Trade-offs in Graph Embeddings, with Applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cost Trade-offs in Graph Embeddings, with Applications

Full text

Pdf (1.09 MB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 4 (October 1983) table of contents

Pages: 709 - 728

Year of Publication: 1983

ISSN:0004-5411

Authors

Jia-Wei Hong	Peking Computer Institute, Peking 100044, China
Kurt Mehlhorn	Fach. 10, Angewandte Mathematik und Informatik, Universitàt Saarlandes, Saarbrücken, Federal Republic of Germany
Arnold L. Rosenberg	Department of Computer Science, Duke University, Durham, NC

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 27, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2157.322401 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ALr:J.It~AS, R., AND ROSEI, tBI~G, A.L.On embedding rectangular grids in square grids. IEEE Trans. Comput., C-31 (1982), 907-913.
	2	BORODIN, A., Fiscrmg, M.J., KIRKPATRICK, D., LYNCH, N.A, AND TOMPA, M.A time,-spac~ tradeoff for sorting on rtonoblivious machines. In Proc. 20th IEEE Syrup. on Foundations of Computer Science (San Suan, Puerto Rico, Oct, 1979), IEEE, New York, pp. 319-327.
	3	CASSetS, J.W.S.An Introduction to Dlophantine ApproMmanon. Cambridge Tracts in Mathematics and Mathematical Physics 45, Cambridge University Press, Cambridge, England, 1957.
	4	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	5	Credo, F.R.K., COPPERSMITH, D., AND GRAHAM, R.L. On trees containing all small trees. Unpublished manuscript, 1979.
	6	COBHAM, A.The recognition problem for the set of perfect squares. In Proc. 7th IEEE Symp. on Switching and Automata Theory (Berkeley, Calif., 1966), IEEE, New York, pp. 78-87.
	7	DEMn.Lo, R.A., EISm,~sxAT, S.C., XND LxPxolq, g.J. Oft small universal data stmetut~ attd related combinatorial problems. In Proc. Johns Hopkins Conf. on Information Sciences and Systems, Baltimore, Md., 1978, pp. 408-411.
	8	HoNG, L-W On similarity and duality of computauon. J. Comput. Syst. Sct. (to appear).
	9	HoNG, L-W., Awo ROSEt,rBm~O, A.L. Graphs that are almost binary trees. SIAM J. Comput. 11 (1982), 227-242.
	10	KuNo, H.T., ^ND S~WNSOr4, D. A software technique for reducting the routine time on a parallel computer with a fixed intereonneetion network. In High Speed Computer and Algorithm Optimization, Academic Press, New York, 1977, pp. 423--433
	11	LmOHTOr~, F.T., AND ROSEr~ErtG, A.L. Three-dimensional circuit layouts. Unpublished manuscript, 1982.
	12	Lmvas, P.M., STEARNS, R.E., AN~O ARTMANIS, J.Memory bounds for recogmtion of context-free and context-sensitive languages. In Proc 6th Conf. on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1965, pp. 191-202.
	13	R. J. Lipton , S. C. Eisenstat , R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures, Journal of the ACM (JACM), v.23 n.4, p.720-732, Oct. 1976 [doi>10.1145/321978.321990]
	14	LIPTON, R.L, AND TARJAN, R.E. ApplicaUons of a planar separator theorem. In Pro6 18th IEEE Syrup. on Foundations of Computer Science (Providence, R.I., Oct. 1977), IEEF.,, New York, pp. 162-170.
	15	I.,n~ToN, R.J., AIqD TT~tj~, R.E.A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979), 17%489.
	16	M_Htt~ORN, K. Best possible bounds on the weighted path length of optimum binary search trees. SIAM Z Comput. 6 (1977), 235-239.
	17	Arnold L. Rosenberg, Encoding Data Structures in Trees, Journal of the ACM (JACM), v.26 n.4, p.668-689, Oct. 1979 [doi>10.1145/322154.322160]
	18	Arnold L. Rosenberg, Issues in the Study of Graph Embeddings, Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science, p.150-176, June 15-18, 1980
	19	Arnold L. Rosenberg, Three-Dimensional VLSI: a case study, Journal of the ACM (JACM), v.30 n.3, p.397-416, July 1983 [doi>10.1145/2402.322384]
	20	ROSENBEItG, A.L., AND SNYDER~ L. Bounds on the costs of data encodings. Math. Syst. Theory 12 (1978), 9-39.
	21	Walter L. Ruzzo, Tree-size bounded alternation(Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.352-359, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804428]
	22	SAVITCH, W J. Relattonships between nondeterministi~ and deterministic tape complexities. ~ Comput. Syst. Sci. 4 (1970), 177--192.
	23	SEKA~^, M. On an ordering of the set of verdces of a connected graph Publ. Fac. Sci. Univ. Brag 412 (1960), 137-142.
	24	C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
	25	VALIAN'r, L.G.Universality ~ons~derauons in VLSI circuits. IEEE Trans. Comput., C-30 (1981), 135-140.

CITED BY 13

	Xiangdong Yu , Dipak Ghosal, Optimal dynamic scheduling of task tree on constant-dimensional architectures, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.138-146, June 29-July 01, 1992, San Diego, California, United States
	E. Ma , D. G. Shea, E-Kernel: An Embedding Kernel on the IBM Victor V256 Multiprocessor for Program Mapping and Network Reconfiguration, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.977-994, September 1994
	Jean-Claude Bermond , Nausica Marlin , David Peleg , Stéphane Perennes, Directed virtual path layouts in ATM networks, Theoretical Computer Science, v.291 n.1, p.3-28, 4 January 2003
	Michael T. Goodrich , S. Rao Kosaraju, Sorting on a parallel pointer machine with applications to set expression evaluation, Journal of the ACM (JACM), v.43 n.2, p.331-361, March 1996
	Clyde P. Kruskal , Kevin J. Rappoport, Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.132-139, June 27-29, 1994, Cape May, New Jersey, United States
	Ajay K. Gupta , Donald Nelson , Hong Wang, Efficient embeddings of ternary trees into hypercubes, Journal of Parallel and Distributed Computing, v.63 n.6, p.619-629, June 2003
	Kyung-Hee Seo , Sung-Chun Kim, Improving system performance in contiguous processor allocation for mesh-connected parallel systems, Journal of Systems and Software, v.67 n.1, p.45-54, 15 July 2003
	K. H. Kim , A. Kavianpour, A Distributed Recovery Block Approach to Fault-Tolerant Execution of Application Tasks in Hypercubes, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.104-111, January 1993
	Xiaojun Shen , Weifa Liang , Qing Hu, On Embedding Between 2D Meshes of the Same Size, IEEE Transactions on Computers, v.46 n.8, p.880-889, August 1997
	Amnon Barak , Eugen Schenfeld, Embedding Classical Communication Topologies in the Scalable OPAM Architecture, IEEE Transactions on Parallel and Distributed Systems, v.7 n.9, p.979-992, September 1996
	A. Kavianpour , N. Bagherzadeh, A Systematic Approach for Mapping Application Tasks in Hypercubes, IEEE Transactions on Computers, v.42 n.6, p.742-746, June 1993
	Ajay K. Gupta , Susanne E. Hambrusch, Embedding Complete Binary Trees Into Butterfly Networks, IEEE Transactions on Computers, v.40 n.7, p.853-863, July 1991
	Kyung-Hee Seo , Sung-Chun Kim, A dynamic processor management strategy on the reconfigurable meshes, International Journal of High Performance Computing and Networking, v.3 n.1, p.54-61, September 2005