World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Sorting Network on Trees

    https://doi.org/10.1142/S0129626419500154Cited by:0 (Source: Crossref)

    Sorting networks are a class of parallel oblivious sorting algorithms. Not only do they have interesting theoretical properties but they can be fabricated. A sorting network is a sequence of parallel compare-exchange operations using comparators which are grouped into stages. This underlying graph defines the topology of the network. The majority of results on sorting networks concern the unrestricted case where the underlying graph is the complete graph. Prior results are also known for paths, hypercubes, and meshes. In this paper we introduce a sorting network whose underlying topology is a tree and formalize the concept of sorting networks on a restricted graph topology by introducing a new parameter for graphs called its sorting number. The main result of the paper is a description of an O(min(nΔ2,n2)) depth sorting network on a tree with maximum degree Δ.

    References

    • 1. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and searching, 2nd edn. (1998). Google Scholar
    • 2. M. Ajtai, J. Komlós and E. Szemerédi, An 0(n log n) sorting network, in Proc. of the Fifteenth Annual ACM Symposium on Theory of Computing (ACM, 1983), pp. 1–9. CrossrefGoogle Scholar
    • 3. K. E. Batcher, Sorting networks and their applications, in Proc. of the Spring Joint Computer Conference, April 30–May 2, 1968 (ACM, 1968), pp. 307–314. CrossrefGoogle Scholar
    • 4. T. Leighton and C. G. Plaxton, Hypercubic sorting networks, SIAM Journal on Computing 27(1) (1998) 1–47. Crossref, Web of ScienceGoogle Scholar
    • 5. C. G. Plaxton and T. Suel, A super-logarithmic lower bound for hypercubic sorting networks, in International Colloquium on Automata, Languages, and Programming (Springer, 1994), pp. 618–629. CrossrefGoogle Scholar
    • 6. C. P. Schnorr and A. Shamir, An optimal sorting algorithm for mesh connected computers, in Proc. of the Eighteenth Annual ACM Symposium on Theory of Computing (ACM, 1986), pp. 255–263. CrossrefGoogle Scholar
    • 7. N. Alon, F. R. Chung and R. L. Graham, Routing permutations on graphs via matchings, SIAM Journal on Discrete Mathematics 7(3) (1994) 513–530. Crossref, Web of ScienceGoogle Scholar
    • 8. I. Banerjee, D. Richards and I. Shinkar, Sorting networks on restricted topologies, in Int. Conf, on Current Trends in Theory and Practice of Informatics (Springer, 2019), pp. 54–66. CrossrefGoogle Scholar