Optimal-depth sorting networks
详细信息 查看全文
- 作者：Daniel Bundalaa ; bundala@gmail.com" class="auth_mail" title="E-mail the corresponding author ; Michael Codishb ; mcodish@cs.bgu.ac.il" class="auth_mail" title="E-mail the corresponding author ; Luí ; s Cruz-Filipec ; lcf@imada.sdu.dk" class="auth_mail" title="E-mail the corresponding author ; Peter Schneider-Kampc ; petersk@imada.sdu.dk" class="auth_mail" title="E-mail the corresponding author ; Jakub Zá ; vodný ; a ; jakub.zavodny@oxfordalumni.org" class="auth_mail" title="E-mail the corresponding author
- 关键词：Sorting networks ; SAT solving ; Symmetry breaking
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：185-204
- 全文大小：580 K
文摘
- class="listitem" id="list_ls0010">
- class="label">•
We prove depth optimality of sorting networks from “The Art of Computer Programming”.
- class="label">•
Sorting networks posses symmetry that can be used to generate a few representatives.
- class="label">•
These representatives can be efficiently encoded using regular expressions.
- class="label">•
We construct SAT formulas whose unsatisfiability is sufficient to show optimality.
- class="label">•
Resulting algorithm is orders of magnitude faster than prior work on small instances.