Node-disjoint paths on the mesh and a new trade-off in VLSI layout

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Node-disjoint paths on the mesh and a new trade-off in VLSI layout

Full text

Pdf (919 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 585 - 594

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Alok Aggarwal	I.B.M. T.J. Watson Research Center, P.O. Box 218, Yorktown Heights NY
Jon Kleinberg	Laboratory for Computer Science, MIT, Cambridge, MA
David P. Williamson	I.B.M. T.J. Watson Research Center, P.O. Box 218, Yorktown Heights NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 11, Citation Count: 0

Additional Information:

references 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/237814.238007 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	A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, A. Wigderson, "Multi-layer grid embeddings," Proc. 26th IEEE FOCS, 1985.
	2	A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, A. Wigderson, "A lower bound on the area of permutation layouts," Algorithmica, 6(1991), pp. 241-255.
	3	A. Aggarwal, M. Klawe, P. Shot, "Multi-layer grid embeddings for VLSI," Algorithmica, 6(1991), pp. 129-151.
	4	R. Cole, A. Siegel, "River routing every which way but loose," Proc. 25th IEEE FOCS, 1984.
	5	M. Cutler, Y. Shiloach, "Permutation layout," Networks, 8(1978), pp. 253-278.
	6	P. ErdSs, G. Szekeres, "A combinatorial problem in geometry," Compositio Math., 2(1935), pp. 463-470.
	7	Maria Klawe , Tom Leighton, A tight lower bound on the size of planar permutation networks, SIAM Journal on Discrete Mathematics, v.5 n.4, p.558-563, Nov. 1992 [doi>10.1137/0405045]
	8	J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
	9	M.E. Kramer, J. van Leeuwen, "The complexity of wire routing and finding the minimum area layouts for arbitrary VLSI circuits," Advances in Computing Research 2: VL$I Theory, F.P. Preparata, Ed., London: JAI Press, 1984. pp. 129-146.
	10	F.T. Leighton, Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VL$i, Ph.D. Thesis, MIT Math Dept., 1981.
	11	C E Leiserson , F M Maley, Algorithms for routing and testing routability of planar VLSI layouts, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.69-78, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22153]
	12	William R. Pulleyblank, Two Steiner tree packing problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.383-387, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225163]
	13	Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195119]
	14	Ronald L. Rivest, The “PI” (placement and interconnect) system, Proceedings of the 19th conference on Design automation, p.475-481, January 1982
	15	Neil Robertson , P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, Journal of Combinatorial Theory Series B, v.45 n.2, p.212-254, Oct. 1988 [doi>10.1016/0095-8956(88)90070-6]
	16	A. Schrijver, "Disjoint homotopic paths and trees in a planar graph~" Discrete and Computalional Geometry, 6(1991), pp. 527-574.