Sorting Networks on Restricted Topologies
Abstract
The sorting number of a graph with n vertices is the minimum depth of a sorting network with n inputs and n outputs that uses only the edges of the graph to perform comparisons. Many known results on sorting networks can be stated in terms of sorting numbers of different classes of graphs. In this paper we show the following general results about the sorting number of graphs.
1. Any n-vertex graph that contains a simple path of length d has a sorting network of depth (O(n log(n/d)).
2. Any n-vertex graph with maximal degree Δ has a sorting network of depth (formula Presented).
We also provide several results relating the sorting number of a graph with its routing number, size of its maximum matching, and other well known graph properties. Additionally, we give some new bounds on the sorting number for some typical graphs.
Recommended Citation
A. Banerjee et al., "Sorting Networks on Restricted Topologies," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11376 LNCS, pp. 54 - 66, Springer Verlag, Jan 2019.
The definitive version is available at https://doi.org/10.1007/978-3-030-10801-4_6
Meeting Name
45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 (2018: Jan. 27-30, Nový Smokovec, Slovakia)
Department(s)
Computer Science
Keywords and Phrases
Matchings In Graphs; Routing via Matchings; Sorting Networks
International Standard Book Number (ISBN)
978-303010800-7
International Standard Serial Number (ISSN)
0302-9743
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2019 Springer Verlag, All rights reserved.
Publication Date
01 Jan 2019
Comments
Published as Indranil Banerjee.