Sorting Using Networks of Queues and Stacks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sorting Using Networks of Queues and Stacks

Full text

Pdf (323 KB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 2 (April 1972) table of contents

Pages: 341 - 346

Year of Publication: 1972

ISSN:0004-5411

Author

Robert Tarjan

Stanford University, Computer Science Department, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 70, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/321694.321704 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	EVEN, S., AND ITAI, A. Queues, stacks, and graphs. In Theory of Machines and Computations, Zvi Kohavi and Azaria Paz, Eds. (Proceedings of an International Symposium on the Theory of Machines and Computations, Technion--Israel Inst. of Technol., Haifa, Israel, Aug. 1971), Academic Press, New York, 1971, pp. 71-86.
	2	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	3	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	4	SCHE~STED, C. Longest increasing and decreasing subsequences. Canad. J. Math. 13, 2 (1961), 179-191.

CITED BY 18

	Vaughan R. Pratt, Computing permutations with double-ended queues, parallel stacks and parallel queues, Proceedings of the fifth annual ACM symposium on Theory of computing, p.268-277, April 30-May 02, 1973, Austin, Texas, United States
	M Yannakakis, Four pages are necessary and sufficient for planar graphs, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.104-108, May 28-30, 1986, Berkeley, California, United States
	M. D. Atkinson, Generalized Stack Permutations, Combinatorics, Probability and Computing, v.7 n.3, p.239-246, September 1998
	Rebecca Smith , Vincent Vatter, The enumeration of permutations sortable by pop stacks in parallel, Information Processing Letters, v.109 n.12, p.626-629, May, 2009
	M. D. Atkinson , M. M. Murphy , N. Ruskuc, Sorting with two ordered stacks in series, Theoretical Computer Science, v.289 n.1, p.205-223, 23 October 2002
	M. H. Albert , M. D. Atkinson , N. Ruškuc, Regular closed sets of permutations, Theoretical Computer Science, v.306 n.1-3, p.85-100, 5 September 2003
	Miki Miyauchi, Queue Layout of Bipartite Graph Subdivisions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.5, p.896-899, May 2007
	M. D. Atkinson , T. Stitt, Restricted permutations and the wreath product, Discrete Mathematics, v.259 n.1-3, p.19-36, 28 December 2002
	Martin Klazar, On the least exponential growth admitting uncountably many closed permutation classes, Theoretical Computer Science, v.321 n.2-3, p.271-281, 16 August 2004
	Mehmet Hakan Karaata , Pranay Chaudhuri, A self-stabilizing algorithm for bridge finding, Distributed Computing, v.12 n.1, p.47-53, March 1999
	Kenneth J. Thurber, Interconnection networks: a survey and assessment, Proceedings of the May 6-10, 1974, national computer conference and exposition, May 06-10, 1974, Chicago, Illinois
	Eric S. Egge , Toufik Mansour, 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers, Discrete Applied Mathematics, v.143 n.1-3, p.72-83, 30 September 2004
	David R. Wood, Degree constrained book embeddings, Journal of Algorithms, v.45 n.2, p.144-154, November 2002
	Robert Cimikowski, An analysis of some linear graph layout heuristics, Journal of Heuristics, v.12 n.3, p.143-153, May 2006
	Toru Hasunuma, Queue layouts of iterated line directed graphs, Discrete Applied Mathematics, v.155 n.9, p.1141-1154, May, 2007
	Herbert S. Wilf, The patterns of permutations, Discrete Mathematics, v.257 n.2-3, p.575-583, 28 November
	Robert Cimikowski , Brendan Mumey, Approximating the fixed linear crossing number, Discrete Applied Mathematics, v.155 n.17, p.2202-2210, October, 2007
	Robert Cimikowski, Algorithms for the fixed linear crossing number problem, Discrete Applied Mathematics, v.122 n.1-3, p.93-115, 15 October 2002