Sorting Networks: The End Game

Michael Codish; Luís Cruz-Filipe; Peter Schneider-Kamp

doi:10.1007/978-3-319-15579-1_52

Sorting Networks: The End Game

Michael Codish
, Luís Cruz-Filipe
, Peter Schneider-Kamp

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Konferenceartikel › Forskning › peer review

Abstract

This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focus on properties of the front end of networks and on how to apply these to break symmetries in the search. The new properties help shed understanding on how sorting networks sort and speed-up solvers for both optimal size and depth by an order of magnitude.

Originalsprog	Engelsk
Tidsskrift	Lecture Notes in Computer Science
Vol/bind	8977
Sider (fra-til)	664-675
Antal sider	12
DOI	https://doi.org/10.1007/978-3-319-15579-1_52
Status	Udgivet - 24 feb. 2015
Udgivet eksternt	Ja
Begivenhed	International Conference on Language and Automata Theory and Applications - Nice, Frankrig Varighed: 2 mar. 2015 → 6 mar. 2015 Konferencens nummer: 9 https://dblp.org/db/conf/lata/index.html

Konference

Konference	International Conference on Language and Automata Theory and Applications
Nummer	9
Land/Område	Frankrig
By	Nice
Periode	02/03/2015 → 06/03/2015
Internetadresse	https://dblp.org/db/conf/lata/index.html

Adgang til dokumentet

10.1007/978-3-319-15579-1_52Licens: Ikke-specificeret

Citationsformater

@inproceedings{5469113d90fb48e39253589412eacdd4,

title = "Sorting Networks: The End Game",

abstract = "This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focus on properties of the front end of networks and on how to apply these to break symmetries in the search. The new properties help shed understanding on how sorting networks sort and speed-up solvers for both optimal size and depth by an order of magnitude.",

keywords = "SAT solving, Sorting networks, Symmetry breaking",

author = "Michael Codish and Lu{\'i}s Cruz-Filipe and Peter Schneider-Kamp",

note = "9th International Conference on Language and Automata Theory and Applications, LATA ; Conference date: 02-03-2015 Through 06-03-2015; International Conference on Language and Automata Theory and Applications, LATA ; Conference date: 02-03-2015 Through 06-03-2015",

year = "2015",

month = feb,

day = "24",

doi = "10.1007/978-3-319-15579-1\_52",

language = "English",

volume = "8977",

pages = "664--675",

journal = "Lecture Notes in Computer Science",

url = "https://dblp.org/db/conf/lata/index.html",

}

TY - GEN

T1 - Sorting Networks: The End Game

AU - Codish, Michael

AU - Cruz-Filipe, Luís

AU - Schneider-Kamp, Peter

N1 - Conference code: 9

PY - 2015/2/24

Y1 - 2015/2/24

N2 - This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focus on properties of the front end of networks and on how to apply these to break symmetries in the search. The new properties help shed understanding on how sorting networks sort and speed-up solvers for both optimal size and depth by an order of magnitude.

AB - This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focus on properties of the front end of networks and on how to apply these to break symmetries in the search. The new properties help shed understanding on how sorting networks sort and speed-up solvers for both optimal size and depth by an order of magnitude.

KW - SAT solving

KW - Sorting networks

KW - Symmetry breaking

U2 - 10.1007/978-3-319-15579-1_52

DO - 10.1007/978-3-319-15579-1_52

M3 - Conference article

VL - 8977

SP - 664

EP - 675

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - International Conference on Language and Automata Theory and Applications

Y2 - 2 March 2015 through 6 March 2015

ER -

Sorting Networks: The End Game

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater