Name
Abstract | ||
|---|---|---|
We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time @Q(n^2) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time @W(n^3^/^2), and that there exist graphs of k nodes which can sort in time @Q(nlog"kn), which is optimal. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.dam.2010.06.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
data structure,directed acyclic graph,sorting networks,sorting network,data structures | Counting sort,Permutation graph,Comparison sort,Discrete mathematics,Indifference graph,Combinatorics,Pigeonhole sort,Chordal graph,Integer sorting,Mathematics,Sorting algorithm | Journal |
Volume | Issue | ISSN |
158 | 15 | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 32 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Therese Biedl | 1 | 902 | 106.36 |
| Alexander Golynski | 2 | 311 | 16.23 |
| Angèle M. Hamel | 3 | 77 | 12.59 |
| Alejandro López-Ortiz | 4 | 1252 | 107.44 |
| J. Ian Munro | 5 | 3010 | 462.97 |