Abstract | ||
---|---|---|
In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several combinatorial results which we state in section 2 and prove in the appendix. The other layouts are described in section 4. Although these layouts are not asymptotically optimal (most require 0(n2/log3/2n) area), the theory behind their development is interesting and may eventually lead to good practical layouts as well as other asymptotically optimal layouts. |
Year | DOI | Venue |
---|---|---|
1981 | 10.1145/800076.802480 | STOC |
Keywords | DocType | Citations |
decidability,petri net | Conference | 15 |
PageRank | References | Authors |
4.01 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniel J. Kleitman | 1 | 854 | 277.98 |
Frank Thomson Leighton | 2 | 2365 | 493.65 |
Margaret Lepley | 3 | 24 | 5.79 |
Gary L. Miller | 4 | 3239 | 1155.26 |