Cost Trade-offs in Graph Embeddings, with Applications
Tóm tắt
Từ khóa
Tài liệu tham khảo
A Lr : 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 . 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.
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 . 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.
CAS Set S , J.W.S. An Introduction to Dlophantine ApproMmanon. Cambridge Tracts in Mathematics and Mathematical Physics 45 , Cambridge University Press , Cambridge, England , 1957 . CASSetS, J.W.S.An Introduction to Dlophantine ApproMmanon. Cambridge Tracts in Mathematics and Mathematical Physics 45, Cambridge University Press, Cambridge, England, 1957.
Credo , F.R.K. , COPPERSMITH , D., AND GRAHAM, R.L. On trees containing all small trees. Unpublished manuscript , 1979 . Credo, F.R.K., COPPERSMITH, D., AND GRAHAM, R.L. On trees containing all small trees. Unpublished manuscript, 1979.
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 . 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.
DE Mn .Lo, R.A. , EISm,~sx AT , 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 . 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.
HoNG L-W On similarity and duality of computauon. J. Comput. Syst. Sct. (to appear). HoNG L-W On similarity and duality of computauon. J. Comput. Syst. Sct. (to appear).
Ho NG , L- W. , Awo ROSEt,rBm~ O , A.L . Graphs that are almost binary trees . SIAM J. Comput. 11 ( 1982 ), 227 - 242 . HoNG, L-W., Awo ROSEt,rBm~O, A.L. Graphs that are almost binary trees. SIAM J. Comput. 11 (1982), 227-242.
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 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
Lm OHTOr~, F.T. , AND ROSEr~Ert G , A.L. Three-dimensional circuit layouts. Unpublished manuscript , 1982 . LmOHTOr~, F.T., AND ROSEr~ErtG, A.L. Three-dimensional circuit layouts. Unpublished manuscript, 1982.
Lmvas , P.M. , STEARNS , R.E., A N~ 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 . 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.
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 . 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.
I.,n~ To N , R.J. , A Iq D TT~tj~, R.E.A separator theorem for planar graphs . SIAM J. Appl. Math. 36 ( 1979 ), 17% 489 . I.,n~ToN, R.J., AIqD TT~tj~, R.E.A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979), 17%489.
M_ Htt~ ORN , K . Best possible bounds on the weighted path length of optimum binary search trees . SIAM Z Comput. 6 ( 1977 ), 235 - 239 . M_Htt~ORN, K. Best possible bounds on the weighted path length of optimum binary search trees. SIAM Z Comput. 6 (1977), 235-239.
ROS Et~n~ RG , A.L. Issues in the study of graph embeddings . In Graph- Theoraic Concepts m Computer Science (Proc. of the Int. Workshop WGS0) , Lecture Notes in Computer Science 100 , H. Noltemeier, Ed., Springer-Veda $, New York, 1981 , pp. 150 - 176 . ROSEt~n~RG, A.L. Issues in the study of graph embeddings. In Graph- Theoraic Concepts m Computer Science (Proc. of the Int. Workshop WGS0), Lecture Notes in Computer Science 100, H. Noltemeier, Ed., Springer-Veda$, New York, 1981, pp. 150-176.
ROSENBE It G , A.L. , AND SNYDE R~ L . Bounds on the costs of data encodings . Math. Syst. Theory 12 ( 1978 ), 9 - 39 . ROSENBEItG, A.L., AND SNYDER~ L. Bounds on the costs of data encodings. Math. Syst. Theory 12 (1978), 9-39.
SAVITCH, W J . Relattonships between nondeterministi~ and deterministic tape complexities. ~ Comput . Syst. Sci. 4 ( 1970 ), 177 -- 192 . SAVITCH, W J. Relattonships between nondeterministi~ and deterministic tape complexities. ~ Comput. Syst. Sci. 4 (1970), 177--192.
SEK A~ ^, M . On an ordering of the set of verdces of a connected graph Publ . Fac. Sci. Univ. Brag 412 ( 1960 ), 137 - 142 . SEKA~^, M. On an ordering of the set of verdces of a connected graph Publ. Fac. Sci. Univ. Brag 412 (1960), 137-142.
Thorn , so N , C ,D. Area-time complexity for VLSI In Proc. llth ACM Syrup. on Theory of Computing (Atlanta , Ga. , May 1979 ), ACM, New York , pp. 81 - 88 . 10.1145/800135.804401 Thorn, soN, C,D.Area-time complexity for VLSI In Proc. llth ACM Syrup. on Theory of Computing (Atlanta, Ga., May 1979), ACM, New York, pp. 81-88. 10.1145/800135.804401
VALIA N'r , L.G. Universality ~ons~derauons in VLSI circuits. IEEE Trans. Comput. , C-30 ( 1981 ), 135 - 140 . VALIAN'r, L.G.Universality ~ons~derauons in VLSI circuits. IEEE Trans. Comput., C-30 (1981), 135-140.